排序算法

SORT

分类:

• 插入: 直接插入排序, 折半插入排序, 希尔排序
• 交换: 冒泡排序, 快速排序
• 选择: 选择排序, 堆排序

排序算法比较

排序算法	最好情况	最坏情况	平均时间复杂度	空间复杂度	排序方式	稳定性
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	in-place	稳定
折半插入排序	$O(n)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	in-place	稳定
希尔排序	$O(nlogn)$	$O(nlogn^2)$	$O(nlogn^2)$	$O(1)$	in-place	不稳定
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	in-place	稳定
快速排序	$O(nlogn)$	$O(n^2)$	$O(nlogn)$	$O(logn)$	in-place	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	in-place	不稳定

1. 插入排序(Insertion Sort)

插入排序的关键是找到正确的插入位置

1.1 直接插入排序(Straight Insertion Sort)

这是最简单的一种排序方法, 基本操作是将一个记录插入到已排好序的有序表中, 从而得到一个全新的, 记录数增1的有序表

• 将数组首项设为一个有序表, 将下一项设置为待插入元素, 倒序遍历有序表, 将大于这个元素的记录完后移一位, 直至找到第一个小于等于这个元素的记录, 将该元素查到这个记录后面, 将有序表长加1
• 继续取有序表后一个元素作为带插入元素, 重复以上步骤, 直至将整个序列变成非递减序列

void Straight_Insertion_Sort(vector<int> & nums, int n){
    for(int i = 0; i < n; ++i){
        int X = nums[i];
        int j = i-1;
        for(; j >= 0 && nums[j] > X; --j){
            nums[j+1] = nums[j];
        }
        nums[j+1] = X;
    }
}

或使用 swap 函数

void Insertion_Sort(vector<int> & nums, int n){
    for(int i = 0; i < n; ++i){
        for(int j = i; j > 0 && nums[j] < nums[j - 1]; --j){
            swap(nums[j], nums[j-1]);
        }
    }
}

时间复杂度: $O(n^2)$

1.2 折半插入排序(Binary Insertion Sort)

由于是在有序表中查找待插入元素的位置, 显然使用二分法来查找更有效.

void Binary_Insertion_Sort(vector<int> & nums, int n){
    int left, right, mid, i, j;

    for(i = 1; i < n; ++i){
        //寻找到满足 nums[mid] <= nums[i] <= nums[mid+1]
        int X = nums[i];
        left = 0;
        right = i - 1;

        while(left <= right){
            mid = right + left >> 1;
            if(nums[mid] <= nums[i]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        for(j = i - 1; j >= right + 1; --j){
            nums[j+1] = nums[j];
        }
        nums[j+1] = X;
    }
}

1.3 希尔排序(Sheel Sort)

void Shell_Sort(vector<int> & nums, int n){
    int h = 1;
    while(h < n/3){
        h = h * 3 + 1; // 1, 4, 13, 40, ...
    }
    while(h >= 1){
        for(int i = h; i < n; ++i){
            for(int j = i; j >= h && nums[j] < nums[j-h]; j -= h){
                swap(nums[j], nums[j-h]);
            }
        }
        h = h / 3;
    }
}

2. 冒泡排序(Bubble Sort)

• 第一次遍历数组, 对比第 i 项与 i+1 项, 通过交换他俩的值保证较大的那个数被交换到后面, 增大 i 的值, 再次执行对比交换过程, 直到最大的那个数被交换到数组的末尾, 这是第一次冒泡排序的过程
• 遍历数组, 重复以上步骤

void Bubble_Sort(vector<int>& nums, int n){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n - i - 1; ++j){
            if(nums[j] > nums[j+1]){
                swap(nums[j], nums[j+1]);
            }
        }
    }
}

3. 快速排序(Quick Sort)

3.1 快速排序算法

快速排序是对冒泡排序的一种改进. 它的基本思想是: 通过一趟排序将待排记录分割成独立的两部分, 其中一部分记录的段简直均比另一部分的关键字小,则可分别对这两部分记录继续进行排序, 以达到整个序列有序.

一次快速排序过程: 设置两个指针 left , right , 设置枢纽记录的关键字为 pivorkey, 首先从 right 所指位置向前搜索第一个小于 pivorkey 的记录与枢纽记录进行交换, 然后从 left 所指位置向后搜索, 找到第一个关键字大于 pivorkey 的记录与枢纽记录进行交换, 重复这两步直到 left = right

// 划分子序列, 返回枢纽所在位置
int Partition(vector<int>& nums, int left, int right){
    int pivot = nums[left];
    while(left < right){
        while(left < right && nums[right] >= pivot) --right;
        nums[left] = nums[right];
        while(left < right && nums[left] <= pivot) ++left;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

此时, 在枢纽 pivotkey 之前都是小于等于 pivot 的记录, 右侧都是大于等于 pivot 的记录, 分别再次处理左右记录即可.

使用递归的快速排序如下:

void Quick_Sort(vector<int>& nums, int left, int right){
    if(left < right){
        int pivotkey = Partition(nums, left, right);
        Quick_Sort(nums, left, pivotkey - 1);
        Quick_Sort(nums, pivotkey + 1, right);
    }
}

3.2 改进快速排序

最坏的情况下, 第一次从最小的元素切分, 第二次从第二小的元素切分, 如此这般. 因此最坏的情况下需要比较 $\frac{N^2}{2}$ . 为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组.

只需在 Partition 函数中改进即可.

int Partition(vector<int>& nums, int left, int right){
    int pivotkey = rand() % (right - left + 1) + left;
    swap(nums[pivotkey], nums[left]);
    int pivot = nums[left];
    while(left < right){
        while(left < right && nums[right] >= pivot) --right;
        nums[left] = nums[right];
        while(left < right && nums[left] <= pivot) ++left;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

3.3 快速选择算法

快速排序的 Partition() 方法, 会返回一个整数 j 使得 $a[…j-1]$ 小于等于 $a[j]$ , 且 $a[j+1…]$ 大于等于 $a[j]$ , 此时 $a[j]$ 就是数组的第 j 小元素. 可以利用这一特性解决 第K问题

int quick_select(vector<int> & nums, int left, int right){
    int pivotkey = rand() % (right - left) + left;
    swap(nums[pivotkey], nums[left]);
    int pivot = nums[left];
    while(left < right){
        while(left < right && nums[right] <= pivot) --right;
        nums[left] = nums[right];
        while(left < right && nums[left] >= pivot) ++left;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

LeetCode 215: 数组中的第K个最大元素

4. 选择排序

4.1 简单选择排序

一次简单排序为: 通过 n-i 次对比, 从 n-i+1 个记录中选选择关键字最小的记录, 并与第 i 个记录交换.

void Selection_Sort(vector<int>& nums, int n){
    int min_index;
    for(int i = 0; i < n; ++i){
        min_index = i;
        for(int j = i; j < n; ++j){
            if(nums[j] < nums[min_index]){
                min_index = j;
            }
        }
        swap(nums[i], nums[min_index]);
    }
}

5. 归并排序

归并排序用的是分治的思想, 重点在于怎么将两个有序数组合并为一个有序数组.

void Merge_Sort(vector<int>& nums, int left, int right, vector<int>& temp){
    if(left + 1 >= right) return;


    //divide
    int mid = left + right >> 1;
    Merge_Sort(nums, left, mid, temp);
    Merge_Sort(nums, mid, right, temp);

    //conquer
    int p = left, q = mid, i = left;
    while(p < mid || q < right){
        if(q >= right || (p < mid && nums[p] <= nums[q])){
            temp[i++] = nums[p++];
        } else {
            temp[i++] = nums[q++];
        }
    }

    for(i = left; i < right; ++i){
        nums[i] = temp[i];
    }
}

temp 为辅助数组, 长度与 nums 数组一样.