排序算法

排序算法可以分为内部排序和外部排序。

内部排序是数据记录在内存中进行排序。

而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

关于时间复杂度：

• 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

• 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

• O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

• 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性：

• 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

• 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

冒泡排序 (Bubble Sort)

每次从左到右两两比较，把大的交换到后面，每次可以确保将前M个元素的最大值移动到最右边。

• 从左开始比较相邻的两个元素x和y，如果 x > y 就交换两者
• 执行比较和交换，直到到达数组的最后一个元素
• 重复执行1和2，直到执行n次，也就是n个最大元素都排到了最后

void bubble_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size() - 1; i++) { // times
        for (int j = 0; j < nums.size() - i - 1; j++) { // position
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

插入排序（Insertion Sort）

插入排序的原理是从左到右，把选出的一个数和前面的数进行比较，找到最适合它的位置放入，使前面部分有序。

• 从左开始，选出当前位置的数x，和它之前的数y比较，如果x < y则交换两者
• 对x之前的数都执行1步骤，直到前面的数字都有序
• 选择有序部分后一个数字，插入到前面有序部分，直到没有数字可选择

void insert_sort(vector<int> &nums)
{
    for (int i = 1; i < nums.size(); i++) { // position
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
    }
}

选择排序（Selection Sort）

选择排序的原理是，每次都从乱序数组中找到最大（最小）值，放到当前乱序数组头部，最终使数组有序。

• 从左开始，选择后面元素中最小值，和最左元素交换
• 从当前已交换位置往后执行，直到最后一个元素

void selection_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++) { // position
        int min = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }

        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }
}

!!!

希尔排序（Shell Sort）

希尔排序从名字上看不出来特点，因为它是以发明者命名的。它的另一个名字是“递减增量排序算法“。这个算法可以看作是插入排序的优化版，因为插入排序需要一位一位比较，然后放置到正确位置。为了提升比较的跨度，希尔排序将数组按照一定步长分成几个子数组进行排序，通过逐渐减短步长来完成最终排序。

例子

例如 [10, 80, 70, 100, 90, 30, 20] 如果我们按照一次减一半的步长来算， 这个数组第一次排序时以3为步长，子数组是：

10 80 70 90 30 20 100

这里其实按照列划分的4个子数组，排序后结果为

10 30 20 90 80 70 100

也就是 [10, 30 20 90 80 70 100]

然后再以1为步长生成子数组

10 30 20 ..

这个时候就是一纵列了，也就是说最后一定是以一个数组来排序的。

步骤

• 计算当前步长，按步长划分子数组
• 子数组内插入排序
• 步长除以2后继续12两步，直到步长最后变成1

void shell_sort(vector<int> &nums)
{
    for (int gap = nums.size() >> 1; gap > 0; gap >>= 1) { // times
        for (int i = gap; i < nums.size(); i++) { // position
            int temp = nums[i];

            int j = i - gap;
            for (; j >= 0 && nums[j] > temp; j -= gap) {
                nums[j + gap] = nums[j];
            }

            nums[j + gap] = temp;
        }
    }
}

归并排序（Merge Sort）

归并排序是采用分治法（Divide and Conquer）的一个典型例子。这个排序的特点是把一个数组打散成小数组，然后再把小数组拼凑再排序，直到最终数组有序。

步骤

• 把当前数组分化成n个单位为1的子数组，然后两两比较合并成单位为2的n/2个子数组
• 继续进行这个过程，按照2的倍数进行子数组的比较合并，直到最终数组有序

递归实现：

// L = 左边起始位置， R = 右边起始位置， RightEnd = 右边终点位置
void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd)
{
    int LeftEnd, NumElements, Tmp;
    int i;

    LeftEnd = R-1;
/* 有序序列的起始位置*/
    Tmp = L;
    NumElements = RightEnd-L+1;

    while( L <= LeftEnd && R <= RightEnd)
    {
        if(A[L] <= A[R])
            TmpA[Tmp++] = A[L++];
        else 
            TmpA[Tmp++] = A[R++];
    } 

    while(L <= LeftEnd)
        TmpA[Tmp++] = A[L++];
    while(R <= RightEnd)
        TmpA[Tmp++] = A[R++];
    
    for(i = 0; i < NumElements; i++, RightEnd--)
    {
        A[RightEnd] = TmpA[RightEnd]; //将有序的TmpA[]复制回A[]
    }
}

void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd)
{
    int Center;
    if( L < RightEnd )
    {
        Center = (L + RightEnd) / 2;
        Msort(A, TmpA, L, Center);
        Msort(A, TmpA, Center+1, RightEnd);
        Merge(A, TmpA, L, Center + 1, RightEnd);
    }
}

循环实现：

//归并排序- 循环实现
//这里Merge函数在递归版本中给出
//length = 当前有序子列的长度
void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length)
{
    //两两归并相邻有序子列
    int i, j;
    for(i = 0; i <= N-2*length; i += 2*length)
        Merge(A, TmpA, i, i+length, i+2*length-1);
    if(i + length < N) //归并最后两个子列
        Merge(A, TmpA, i, i+length, N-1);
    else //最后只剩下一个子列
        for(j = i; j < N; j++)
            TmpA[j] = A[j];
}

void Merge_Sort(ElementType A[], int N)
{
    int length;
    ElementType * TmpA;

    length = 1;
    TmpA = malloc(N * sizeof(ElementType));
    if(TmpA != NULL)
    {
        while(length < N)
        {
            Merge_pass(A, TmpA, N, length);
            length *= 2;
            Merge_pass(TmpA, A, N, length);
            length *= 2;
        }
        free( TmpA);
    }
    else
        printf("空间不足");
}

这个实现中加了一个temp，是和原数组一样大的一个空间，用来临时存放排序后的子数组的。

快速排序（Quick Sort）

快速排序也是利用分治法实现的一个排序算法。快速排序和归并排序不同，它不是一半一半的分子数组，而是选择一个基准数，把比这个数小的挪到左边，把比这个数大的移到右边。然后不断对左右两部分也执行相同步骤，直到整个数组有序。

步骤

• 用一个基准数将数组分成两个子数组
• 将大于基准数的移到右边，小于的移到左边
• 递归的对子数组重复执行1，2，直到整个数组有序

void quick_sort(vector<int> &nums, int b, int e, vector<int> &temp)
{
    int m = (b + e) / 2;
    if (m != b) {
        int lb = b, rb = e - 1;

        for (int i = b; i < e; i++) {
            if (i == m)
                continue;
            if (nums[i] < nums[m])
                temp[lb++] = nums[i];
            else
                temp[rb--] = nums[i];
        }
        temp[lb] = nums[m];
        
        for (int i = b; i < e; i++)
            nums[i] = temp[i];
        
        quick_sort(nums, b, lb, temp);
        quick_sort(nums, lb + 1, e, temp);
    }
}

void quick_sort(vector<int> &nums, int b, int e)
{
    if (b < e - 1) {
        int lb = b, rb = e - 1;
        while (lb < rb) {
            while (nums[rb] >= nums[b] && lb < rb)
                rb--;
            while (nums[lb] <= nums[b] && lb < rb)
                lb++;
            swap(nums[lb], nums[rb]);
        }
        swap(nums[b], nums[lb]);
        quick_sort(nums, b, lb);
        quick_sort(nums, lb + 1, e);
    }
}

堆排序（Heap Sort）

堆排序经常用于求一个数组中最大k个元素时。因为堆实际上是一个完全二叉树，所以用它可以用一维数组来表示。因为最大堆的第一位总为当前堆中最大值，所以每次将最大值移除后，调整堆即可获得下一个最大值，通过一遍一遍执行这个过程就可以得到前k大元素，或者使堆有序。

在了解算法之前，首先了解在一维数组中节点的下标：

• i节点的父节点 parent(i) = floor((i-1)/2)
• i节点的左子节点 left(i) = 2i + 1
• i节点的右子节点 right(i) = 2i + 2

步骤

• 构造最大堆（Build Max Heap）：首先将当前元素放入最大堆下一个位置，然后将此元素依次和它的父节点比较，如果大于父节点就和父节点交换，直到比较到根节点。重复执行到最后一个元素。
• 最大堆调整（Max Heapify）：调整最大堆即将根节点移除后重新整理堆。整理方法为将根节点和最后一个节点交换，然后把堆看做n-1长度，将当前根节点逐步移动到其应该在的位置。
• 堆排序（HeapSort）：重复执行2，直到所有根节点都已移除。

void heap_sort(vector<int> &nums)
{
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--) { // build max heap
        max_heapify(nums, i, nums.size() - 1);
    }
    
    for (int i = n - 1; i > 0; i--) { // heap sort
        int temp = nums[i];
        num[i] = nums[0];
        num[0] = temp;
        max_heapify(nums, 0, i);
    }
}

void max_heapify(vector<int> &nums, int beg, int end)
{
    int curr = beg;
    int child = curr * 2 + 1;
    while (child < end) {
        if (child + 1 < end && nums[child] < nums[child + 1]) {
            child++;
        }
        if (nums[curr] < nums[child]) {
            int temp = nums[curr];
            nums[curr] = nums[child];
            num[child] = temp;
            curr = child;
            child = 2 * curr + 1;
        } else {
            break;
        }
    }
}