常见排序算法

稳定排序算法：

  • 冒泡排序（Bubble Sort） — O(n²)
  • 插入排序（Insertion Sort）— O(n²)
  • 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
  • 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
  • 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
  • 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
  • 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间

不稳定排序算法：

  • 选择排序（Selection Sort）— O(n²)
  • 堆排序（Heapsort）— O(nlogn)
  • 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

排序算法的稳定性

稳定性定义： 如果排序前后，相等元素的相对顺序保持不变，则该排序算法是稳定的。

(不稳定)快速排序（Quicksort）— O(nlogn)

它使用分治法（Divide and Conquer）的策略来把一个序列分为较小的子序列。

选择一个元素作为”基准”（pivot）。
将数列划分为两部分，使得左边部分的所有元素都小于或等于基准，右边部分的所有元素都大于基准。该操作称为分区（partition）操作。
然后递归地对左右两部分进行快速排序。

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
void quicksort(int a[], int left, int right) {
    int i, j, t, privotkey;
    if (left > right)
        return;
 
    privotkey = a[left];
    i = left;
    j = right;
    while (i < j) {
        //先从右边开始找（最后交换基准时换过去的数要保证比基准小，因为基准选取数组第一个数）
        while (a[j] >= privotkey && i < j) {
            j--;
        }
        a[i] = a[j];
        //再找左边的
        while (a[i] <= privotkey && i < j) {
            i++;
        }
        a[j] = a[i];
    }
    //最终将基准数归位
    a[i] = privotkey;
 
    quicksort(a, left, i - 1);
    quicksort(a, i + 1, right);
}

优化1

虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中法。

  • 取三个数a[left]、a[right]和a[center]，并且对他进行排序，取中值为轴
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
int Median(vector<int>a,int left,int right){
    int midIndex = (left + right)>>1;
    if (a[left] > a[midIndex])
    {
        swap(a[left],a[midIndex]);
    }
    if (a[left] > a[right])
    {
        swap(a[left],a[right]);
    }
    if (a[midIndex] > a[right])
    {
        swap(a[midIndex],a[right]);
    }
    swap(a[midIndex],a[right-1]);
    return a[right-1]; //返回中轴
}
void qSort(vector<int>a,int left,int right){
        //如果需要排序的数据大于3个则使用快速排序
        if (right - left >=3)
        {
            int midIndex = Median(a,left,right);
            int begin = left;
            int end = right - 1;
            while (true){
                while(a[++begin] < midIndex);
                while(a[--end]<midIndex);
                if (begin < end)
                {
                    swap(a[begin],a[end]);
                }
                else{
                    swap(a[begin],a[right -1]);//将枢轴移动到何时位置
                    break;
                }
            }
            qSort(a,left,begin -1);
            qSort(a,begin + 1,right);
        }
        else{
            BubbleSort(a,left,right);//当数据小于3个,直接用冒泡排序
        }
    }

优化2

  • 当待排序序列长度减少到一定大小后，使用插入排序。

优化3

在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割（处理重复效率极高）　

  • 待排序序列 1 4 6 7 6 6 7 6 8 6

  • 　　　三数取中转换后，待分割序列：6 4 6 7 1 6 7 6 8 6 枢轴key：6

  • 　　第一步，在划分过程中，把与key相等元素放入数组的两端，结果为：6 4 1 6(枢轴) 7 8 7 6 6 6

  • 　第二步，划分结束后，把与key相等的元素移到枢轴周围，结果为：1 4 66(枢轴) 6 6 6 7 8 7

  • 1 4 和 7 8 7两个子序列进行快排

  • ref：https://www.cnblogs.com/vipchenwei/p/7460293.html

冒泡排序（Bubble Sort） — O(n²)

冒泡排序是最简单最容易理解的排序算法之一，其思想是通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。 冒泡排序的复杂度，在最好情况下，即正序有序，则只需要比较n次。故，为O(n) ，最坏情况下，即逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(n²)。

乌龟和兔子

在冒泡排序中，最大元素的移动速度是最快的，哪怕一开始最大元素处于序列开头，也可以在一轮内层循环之后，移动到序列末尾。而对于最小元素，每一轮内层循环只能向前挪动一位，如果最小元素在序列末尾，就需要 n-1 次交换才能移动到序列开头。这两种类型的元素分别被称为兔子和乌龟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(vector<int>& arr) {
    bool swapped;
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        // Last i elements are already sorted
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        // If no elements were swapped, break
        if (!swapped)
            break;
    }
}

优化变种：鸡尾酒排序（Cocktail Shaker Sort）

进行双向的循环，解决乌龟和兔子问题，正向循环把最大元素移动到末尾，逆向循环把最小元素移动到最前

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
void cocktailSort(vector<int>& arr) {
    bool swapped = true;
    int start = 0;
    int end = arr.size() - 1;

    while (swapped) {
        swapped = false;

        // Traverse the array from left to right
        for (int i = start; i < end; ++i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        if (!swapped)
            break;

        // Move the end boundary
        --end;

        swapped = false;

        // Traverse the array from right to left
        for (int i = end - 1; i >= start; --i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        // Move the start boundary
        ++start;
    }
}

插入排序（Insertion Sort）— O(n²)

插入排序也是一个简单的排序算法，它的思想是，每次只处理一个元素，从后往前查找，找到该元素合适的插入位置，最好的情况下，即正序有序，这样只需要比较n次，不需要移动。因此时间复杂度为O(n) ，最坏的情况下，即逆序有序，这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n²) 。

  • 从第二个元素开始，将数组分为”已排序”和”未排序”两部分。
  • 取出未排序部分的第一个元素（称为 key）。
  • 将 key 与已排序部分的元素从右向左比较，找到 key 的正确位置。
  • 在比较过程中，将大于 key 的元素都向右移动一位。
  • 最后将 key 插入到找到的正确位置。
  • 重复步骤 2-5，直到所有元素都被排序。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void insertionSort(vector<int>& arr) {
        int n = arr.size();
        
        // Start from the 2nd element
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            // Place the key in its correct position
            arr[j + 1] = key;
        }
    }

    优化 - 二分查找优化：

使用 lower_bound 函数（二分查找）来找到要插入元素的正确位置。
这将查找正确位置的时间复杂度从 O(n) 降低到 O(log n)。
虽然整体时间复杂度仍然是 O(n^2)（因为移动元素仍需要 O(n) 时间），但在实际应用中可以显著减少比较次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void optimizedInsertionSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // Use binary search to find the position where key should be inserted
        int insertPos = lower_bound(arr.begin(), arr.begin() + i, key) - arr.begin();
        
        // Shift elements to the right
        while (j >= insertPos) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // Place the key in its correct position
        arr[insertPos] = key;
    }
}

桶排序（Bucket Sort）— T:O(n); S:O(k)

计数排序 (Counting Sort) — T:O(n+k); S:O(n+k)

合并排序（Merge Sort）— T:O(nlogn); S:O(n)

二叉排序树排序 （Binary tree sort） — T(ideal):O(n log n); T(worse):O(n²); S:O(n)

基数排序（Radix sort）— T:O(n·k); S:O(n)

(不稳定)选择排序（Selection Sort）— O(n²)

(不稳定)堆排序（Heapsort）— O(nlogn)

选择排序（Selection Sort）— O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted part of the array
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap the found minimum element with the first element of the unsorted part
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}