圈圈小站

quanquan's blog

0%

十大排序算法

发表于 分类于

之前学的排序感觉有点生疏了，复习重温一下十大排序算法。

十大排序算法比较

前七种为比较排序，后三种为非比较排序。

排序方法 时间复杂度（平均） 空间复杂度 稳定性
冒泡排序 $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n\log_2n)$ $O(\log_2n)$ 不稳定
插入排序 $O(n^2)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(1)$ 不稳定
希尔排序 $O(n^{1.3})$ $O(1)$ 不稳定
堆排序 $O(n\log_2n)$ $O(1)$ 不稳定
归并排序 $O(n\log_2n)$ $O(n)$ 稳定
计数排序 $O(n+k)$ $O(n+k)$ 稳定
桶排序 $O(n+k)$ $O(n+k)$ 稳定
基数排序 $O(n*k)$ $O(n+k)$ 稳定

  • 快速排序

    • 从列表中选出一个元素，作为“基准”pivot，基准一般随机选择，或采用最左端、最右端和中间位置3元素的中值；

    • 当数据量很小（N<=20）时，快速排序效果不如插入排序，因为快速排序不稳定且有递归开销。

    • 递归写法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    // 选则最左端、最右端和中间位置3元素的中值作为基准值，并将3元素排序，返回基准值
    int medianPovit(vector<int>& array, int left, int mid, int right){
        if (array[left] > array[mid]){
            swap(array[mid], array[left]);
        }
        if (array[left] > array[right]){
            swap(array[left], array[right]);
        }
        if (array[mid] > array[right]){
            swap(array[mid], array[right]);
        }
        return array[mid];
    }
    // 分区,返回基准索引
    int partition(vector<int>& array, int left, int right) {
        // 中间位置索引
        int mid = (left + right) / 2;
        // 基准值（此时基准值对应索引为mid）
        int povit = medianPovit(array, left, mid, right);
        // 将基准值与倒数第二个元素交换
        array[mid] = array[right - 1];
        array[right - 1] = povit;

        int i = left, j = right - 1;
        while (i < j) {
            if (array[i] < povit) {
                i++;
            }
            else if (array[j] >= povit) {
                j--;
            }
            else {
                swap(array[i], array[j]);
            }
        }
        // 交换基准值和i位置元素
        swap(array[i], array[right - 1]);
        return i;
    }
    void quickSortHelp(vector<int>& array, int left, int right) {
        if (left < right) {
            int pivotLoction = partition(array, left, right);
            quickSortHelp(array, left, pivotLoction - 1);
            quickSortHelp(array, pivotLoction + 1, right);
        }
    }
    // 快速排序
    void quickSort(vector<int>& array) {
        quickSortHelp(array, 0, array.size() - 1);
    }

  • 希尔排序

    第一个突破$O(n^2)$的排序算法，是简单插入排序的改进版。

    先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 希尔排序
    void shellSort(vector<int>& array){
        int n = array.size();
        for (int gap = n / 2; gap >= 1; gap /= 2){
            for (int i = gap; i < n; i++){
                // 使用插入排序算法，将元素依次插入所在小组的已排序列表中
                // 待插入元素
                int itermToInsert = array[i];
                int j = i - gap;
                while (j >= 0 && array[j] >= itermToInsert){
                    array[j + gap] = array[j];
                    j -= gap;
                }
                array[j + gap] = itermToInsert;
            }
        }
    }

  • 堆排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    // 调整堆，根元素沿树向下移动，直至其合适位置，first和last分别为堆顶和堆底在数组array中的索引
    void moveDown(vector<int>& array, int first, int last){
        // first的左子节点索引
        int curIndex = first * 2 + 1;
        while (curIndex <= last){
            // 若first有2子节点，令curIndex为其值最大子节点索引
            if (curIndex < last && array[curIndex] < array[curIndex + 1]){
                curIndex++;
            }
            // 若根节点值小于子节点值，则交换
            if (array[first] < array[curIndex]){
                swap(array[first], array[curIndex]);
                first = curIndex;
                curIndex = first * 2 + 1;
            }
            else{
                break;
            }
        }
    }
    // 用数组实现堆
    void buildHeap(vector<int>& array){
        // 最后一个非叶节点的节点索引
        int i = array.size() / 2 - 1;
        while (i >= 0){
            moveDown(array, i, array.size() - 1);
            i--;
        }
    }
    // 堆排序
    void heapSort(vector<int>& array){
        // 生成堆
        buildHeap(array);
        // 堆顶、底索引
        int first = 0, last = array.size() - 1;
        while (first <= last){
            swap(array[first], array[last]);
            last--;
            moveDown(array, first, last);
        }
    }

  • 归并排序

    分治。

    • 递归
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    void merge(vector<int>& array, vector<int>& copyArray, int left, int right) {
    	int mid = (left + right) / 2;
    	int i = left, j = mid + 1, k = 0;
    	while (i <= mid || j <= right) {
    		if (i > mid) {
    			copyArray[k] = array[j];
    			j++;
    		}
    		else if (j > right) {
    			copyArray[k] = array[i];
    			i++;
    		}
    		else if (array[i] > array[j]) {
    			copyArray[k] = array[j];
    			j++;
    		}
    		else {
    			copyArray[k] = array[i];
    			i++;
    		}

    		k++;
    	}
    	for (size_t i = left; i <= right; i++) {
    		array[i] = copyArray[i - left];
    	}
    }
    void mergeSortHelp(vector<int>& array, vector<int>& copyArray, int left, int right) {
    	if (left < right) {
    		int mid = (left + right) / 2;
    		mergeSortHelp(array, copyArray, left, mid);
    		mergeSortHelp(array, copyArray, mid + 1, right);
    		merge(array, copyArray, left, right);
    	}
    }
    // 归并排序 递归实现
    void mergeSort(vector<int>& array) {
    	vector<int> copyArray(array);
    	mergeSortHelp(array, copyArray, 0, array.size() - 1);
    }

  • 计数排序

    • 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
    • 步骤：
    • 找出待排序的数组中最大和最小的元素；
    • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
    • 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void countSort(vector<int>& array){
    if (array.empty()){
        return;
    }
    //找出最大最小值
    int min = array.front(),max = array.front();
    for (int i = 1; i < array.size(); i++){
        if (min > array[i]){
            min = array[i];
        }
        else if (max < array[i]){
            max = array[i];
        }
    }

    // 记录各元素出现次数
    vector<int> counts(max - min + 1);
    for (int i = 0; i < array.size(); i++){
        counts[array[i] - min]++;
    }

    // 根据记录的次数输出对应元素
    int index = 0;
    for (int j = 0; j < counts.size(); j++){
        int n = counts[j];
        while (n--){
            array[index] = j + min;
            index++;
        }
    }
}

  • 桶排序

    • 设置一个定量的数组当作空桶；
    • 遍历输入数据，并且把数据一个一个放到对应的桶里去；
    • 对每个不是空的桶进行排序；
    • 从不是空的桶里把排好序的数据拼接起来。

  • 适用于小范围（最大值和最小值差值较小），独立均匀分布的数据；

  • 可以计算大批量数据，符合线性期望时间；

  • 外部排序方式，需额外耗费n个空间；

  • 基数排序

    • 将各待比较元素数值统一数位长度，即对数位短者在前补零；

    • 根据个位数值大小，对数组进行排序；

    • 重复上一步骤，依次根据更高位数值进行排序，直至到达最高位；

  • 适用于正整数数据（若包含负数，那么需要额外分开处理)；

  • 对于实数，需指定精度，才可使用此算法。

快排 vs 堆排序

  • 堆排序比较的几乎都不是相邻元素，对cache极不友好，数学上的时间复杂度不代表实际运行的情况。快排常数小。

  • cache相比内存，读取速度非常快，所以cache会把一部分我们经常读取的数据暂时储存起来，以便下一次读取的时候，可以不必跑到内存去读，而是直接在cache里面找。

  • 在堆排中，每一个操作都是不利于程序的局部性原理的，每次元素间的比较、数的调整等，都不是相邻或者尽可能附近的元素间的比较(堆调整每次都从堆底拿元素到堆顶然后向下进行调整），那么这就需要不断地在磁盘和内存间换入换出数据。反观快排，利用分而治之的方法，元素间的比较都在某个段内，局部性相当好。

STL sort算法

​ STL的sort算法，数据量大时采用快排算法，分段采用快排（区间小于16）。一旦分段后的数据量小于某个门槛，为避免快排的递归调用带来过大的额外负荷，就改用插入排序。如果递归层次过深，还会改用堆排序。

​ 为什么用插入排序？因为插入排序在面对“几近排序”的序列时，表现更好。

附：
1.整理的排序题 leetcode