排序

内排序和外排序

1. 内排序：排序过程不需要访问外存便能完成
2. 外排序：待排序的数据元素数量很大，整个序列的排序过程不可能在内存中完成

排序的审判

• 时间性能 关键性能差异体现在比较和交换的数量

• 辅助存储空间 为完成排序操作需要的额外的存储空间，必要时可以“空间换时间”

• 算法的实现复杂性 过于复杂的排序法会影响代码的可读性和可维护性，也可能影响排序的性能

总结

• 排序是数据元素从无序到有序的过程
• 排序具有稳定性，是选择排序算法的因素之一
• 比较和交换是排序的基本操作
• 多关键字排序和单关键字排序无本质区别
• 排序的时间性能是区分排序算法好坏的主要因素

冒泡排序

冒泡法是相邻两个元素进行比较

• 从左向右扫描数据，选择最大的数据，放在右边。然后扫描第二次，第三次等等。每次都选一个最大的数，就像冒气泡一样。
• 要点：比较相邻的两个数，如果左边的数大于右边的数就进行交换

冒泡排序算法简单，但是有不必要的交换，所以慢。

/// 冒泡排序
void BubbleSort(int list[], int n)
{
    /**
     需要两个循环
     最后剩一个数据的时候，就不需要再循环了。
     例：10个数 需要循环9遍，i < 9  从0到8
     */
    for (int i = 0; i < n - 1; i++) {
        // 里面的扫描 会越来越短，所以会越来越快
        // 10个数 第一遍 扫9次 j从0到8
        for (int j = 0; j < n - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                std::swap(list[j], list[j + 1]);
            }
        }
    }
}

void test()
{
    int a[] = {2,4,6,8,0,1,3,5,7,9};
    BubbleSort(a, 10);
    for (int k = 0; k < 10; k++) {
        std::cout << a[k] << "";
        std::cout << std::endl;
    }
}

冒泡法优化

/// 如果已经排好序了，就不需要再排序了，减少排序次数。
/// 情况：在一次循环排序中，一次交换都没有。
/// 算法的时间复杂度还是O(n2)，没有改变。
void BubbleSortBetter(int list[], int n)
{
    bool sortted = false;
    for (int i = 0; (i < n - 1) && (sortted == false); i++) {
        sortted = true;//默认已经排序完毕
        // 里面的扫描 会越来越短，所以会越来越快
        // 10个数 第一遍 扫9次 j从0到8
        for (int j = 0; j < n - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                std::swap(list[j], list[j + 1]);
                sortted = false;//只要发生交换则排序未完成，还需要再排序
            }
        }
    }
}

选择排序

• 要点：选择排序选最小的，往左边选。
• 想象：一条毛巾 谁最小就把毛巾放它面前 并不交换。可能会经常移动毛巾 但是并不交换数据。扫描完后把毛巾放到最左边。

排序过程：

1. 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。
2. 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第一个记录交换。
3. 重复上述操作，共进行n-1趟排序后，排序结束。

第一遍是第一小的，第二遍是第二小的，一直循环。

代码算法：

/// 选择排序
void SelectSort(int *list, const int n)
{
    /**
     需要两个循环
     第一个循环定义扫描的遍数，10个数就扫描10遍
     */
    for (int i = 0; i < n - 1; i++) { //n-1：10个数 扫9遍，最后剩的一个数就不需要扫了。
        int min = i; //min就是毛巾
        // 里面的扫描 扫一遍就排好一个数 所以少扫描一个。
        // 排好的就不需要扫了。所以会越来少。
        for (int j = i + 1; j < n; j++) {
            if (list[j] < list[min]) { // 最小的是毛巾，毛巾min是下标
                // 不交换，只记录下来。如果交换的话就成了冒泡排序了。
                min = j;
            }
        }
        // 扫描一次 结束之后，再交换
        std::swap(list[i], list[min]);
    }
}

冒泡排序与选择排序

冒泡是相邻两个数据比较，经常进行交换，交换次数太多，并且很多交换没有必要。

选择是一个和剩下所有的比较，每次选最小的 在扫描过程中并不交换，到最后才交换。交换少一点。

选择排序比冒泡排序快点，在冒泡上进行了一定的改进。

插入排序

排序过程： 整个排序过程为n-1趟插入，即先将序列中第一个记录看成是一个有序序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。

实质： 对线性表执行n-1次插入操作，只是先要找到插入位置。

新出来的 插入到排好序的里面

template<class T>
void InsertionSort(T *a, int n)//a可以是int，可以是float，可以是double 0(n*n)
{
    int in, out;
    //开始时out=0这个人已经出去了
    for (out = 1; out < n; ++out) {
        T temp = a[out];
        in = out;
        while (in > 0 && a[in - 1] >= temp) {
            a[in] = a[in - 1];
            --in;
        }
        a[in] = temp;
    }
}

调用：

void test()
{
    double x[] = {2.2, 4.5, 6.6, 8, 0, 1, 3, 5, 7, 9};
    InsertionSort(x, 10);
    for (int i = 0; i < 10; i++) {
        std::cout << x[i] << std::endl;
    }
}

升级版 更快一点

template<class T>
void InsertionSort(T *a, int n)
{
    //a[0]用来保存排序使用，不能保存原始数据
    for (int j = 2; j <= n; ++j) {
        T temp = a[j];
        a[0] = temp;
        int i = j - 1;
        while (temp < a[i]) {
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = temp;
    }
}

第一个插入排序的循环条件复杂一点

快速排序

基本思想： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，基准数据排在这两个子序列的中间。 然后再按此方法对这两部分数据分别进行快速排序，直到左右两部分都是一个元素的时候就结束了，整个排序过程可以递归进行，最后再规整，以此达到整个数据变成有序序列。

void QSort(int array[], int low, int high) {
    if (low < high) {
        //选一个pv值，把数据分别放在pv值的左右两边，并把pivot位置返回出来
        int pivot = partition(array, low, high);

        //对子序列1排序
        QSort(array, low, pivot - 1);
        //对子序列2排序
        QSort(array, pivot + 1, high);
    }
}
//划分过程，第一个元素当枢轴，分成2个有效子序列
int partition(int array[], int low, int high) {
    int pv = array[low];
    while (low < high) {
        while ((low < high) && (array[high] >= pv)) {
            high--;//比基准大，本来就在右边，所以high向前移动
        }
        swap(array, low, high);

        while ((low < high) && (array[low] <= pv)) {
            low++;//比基准小，本来就在左边，所以low向后移动
        }
        swap(array, low, high);
    }
    //返回枢轴的位置（重要）
    return low;
}

第一次时 low是0 high是len（长度） - 1 两头移动两个指针 high low， 先取第一个元素，第一个元素就为空，空的一端不移动，另一端和取出来的比较。 结果：两个数组 一个比取出的元素大 一个比取出的元素小。

归并排序

基于分治策略，将待排序的数组不断拆分为较小的子数组，然后再将这些子数组进行合并排序，最终得到有序的结果。

第一遍归并：每组一个数进行排序 。1个1个归并 第二遍归并：每组两个数排序。 2个2个归并 第三遍归并：每组四个数排序。 4个4个归并 ...

每次排序都是之前排好的两个数组再排序

• 优点： 速度快，稳定，突破O（n2）
• 缺点： 牺牲空间。需要一个临时数组，存储空间大一倍。

#include <iostream>
using namespace std;

// 合并两个子数组为一个有序数组
void merge(int arr[], int left, int middle, int right) {
    int i, j, k;
    int n1 = middle - left + 1;
    int n2 = right - middle;

    // 创建临时数组
    int L[n1], R[n2];

    // 将数据复制到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[middle + 1 + j];

    // 合并临时数组为 arr[]
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // 计算中间位置
        int middle = left + (right - left) / 2;

        // 分割并排序左右两个子数组
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

        // 合并左右子数组
        merge(arr, left, middle, right);
    }
}

// 打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组：" << endl;
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "排序后的数组：" << endl;
    printArray(arr, size);

    return 0;
}

希尔排序

排序过程：

先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为至。

希尔和插入法 差不多

希尔排序的gap（间隙）等于1的时候 和 插入法 一样

分组排序 希尔牛逼

10个数据 按照冒泡排序、选择排序 ：需要9趟 希尔排序：需要3趟。

希尔不稳定：相同的数据，可能顺序改变。但是打破的O（n2）。

希尔算法的平均效率 O(n*1.3)。O(nlogn) 每次问题规模缩减三分之一，分区同时排序。 如果有20个数据 gap = gap / 3 + 1；