十大经典排序算法

Posted on Edited on In ,

插入排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
void InsertionSort(vector<int> &arr, int len){
    for(int i=1; i<len; i++){
        int key=arr[i]; //需要插入的元素
        int j=i-1;      //排好序的区间
        while(j>=0 && arr[j]>arr[i]){
            arr[j+1]=arr[j]; //向后移动
            j--;
        }
        arr[j+1]=key;
    }
}

分析

  • 时间复杂度：最好情况下数组已经有序，此时复杂度为O(n)；最坏情况下数组为倒序，此时复杂度为O(n^2)。
  • 空间复杂度：原地排序算法，没有额外内存消耗。
  • 稳定性：只有遇到比当前元素大的才需要把它们移动到后面，所以是稳定排序。（注：我们分析稳定性有一定的实际意义。如果对有多个属性的复杂元素排序，使用稳定排序可以使我们对其中一个属性排序时不影响其它属性。）

选择排序

代码实现

1
2
3
4
5
6
7
8
9
void SelectionSort(vector<int> &arr, int len){
    for(int i=0; i<len-1; i++){
        int min=i;
        for(int j=i+1; j<len; j++){
            if(arr[j]<arr[min]) min=j; //寻找未排序区间里的最小值
        }
        swap(arr[i], arr[min]);
    }
}

分析

  • 时间复杂度：最好和最坏情况下都需要遍历未排序区间，所以时间复杂度都是O(n^2)。
  • 空间复杂度：没有额外的内存消耗。
  • 稳定性：不稳定，因为每次都要在未排序区间找到最小值和前面的值交换，这样前面的值可能会被换到和它相等的值的后面（比如，232154 -> 132254）。

冒泡排序

代码实现

1
2
3
4
5
6
7
8
void BubbleSort(vector<int> &arr, int len){
    for(int i=0; i<len-1; i++){ //i是已排好的区间的长度
        for(int j=0; j<len-i-1; j++){  //j用来遍历未排好的区间中的元素（最后一个没遍历）
            if(arr[j]>arr[j+1]) 
                swap(arr[j], arr[j+1]);
        }
    }
}

分析

  • 时间复杂度：最好情况下，内层循环过一遍发现没有元素发生交换，直接结束，复杂度为O(n)。最坏情况下复杂度为O(n^2)，平均复杂度也是O(n^2)。
  • 空间复杂度：没有用到额外空间。
  • 稳定性：在元素相等的情况下，我们不予交换，因此冒泡排序是稳定排序。

归并排序

代码实现

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
void Merge(vector<int> &arr, int left, int mid, int right){
    int len=right-left+1;
    vector<int> tmp(len);
    int i=left, j=mid+1, k=0;
    while(i<=mid && j<=right){
        tmp[k++]=(arr[i]<=arr[j])?arr[i++]:arr[j++]; //这里的 <= 保证了优先放入左边数组元素
    }
    while(i<=mid){
        tmp[k++]=arr[i++];
    }
    while(j<=right){
        tmp[k++]=arr[j++];
    }
    for(int m=0; m<len; m++){
        arr[left+m]=tmp[m];
    }
}

void MergeSort(vector<int> &arr, int left, int right){
    if(left>=right) return;
    int mid=(left+right)/2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid+1, right);
    Merge(arr, left, mid, right);
}

分析

  • 时间复杂度：O(nlogn)，需要数学推导。
  • 空间复杂度：需要分配临时数组tmp，空间复杂度为O(n)。
  • 稳定性：当需要归并的左右数组中有元素相同时，我们可以保证优先放入左边数组的元素，所以是稳定排序。

快速排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Partition(vector<int> &arr, int left, int right){
    int pivot=right, location=left; //location用来记录比pivot小的元素在分好的数组中的位置
    int r=rand()%(right-left+1)+left; //随机化，注意要在主调函数里写srand((unsigned)time(NULL));
    swap(arr[r], arr[right]);
    for(int i=left; i<=right; i++){
        if(arr[i]<arr[pivot]){
            swap(arr[i], arr[location]);
            location++;
        }
    }
    swap(arr[location], arr[pivot]);
    return location;
}

void QuickSort(vector<int> &arr, int left, int right){
    if(left>=right) return;
    int pivot=Partition(arr, left, right);
    QuickSort(arr, left, pivot-1);
    QuickSort(arr, pivot+1, right);
}

分析

  • 时间复杂度：如果每次分区都能把数组分成大小一样的区间，那么时间复杂度是O(nlogn)，但是最坏情况下可能退化成为O(n^2)。
  • 空间复杂度：没有额外内存消耗。
  • 稳定性：不是稳定排序。

计数排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> CountSort(vector<int> &arr){
    int maxValue=arr[0]; 
    int minValue=arr[0];
    for(int i=1; i<arr.size(); i++){
        maxValue=max(maxValue, arr[i]);
        minValue=min(minValue, arr[i]);
    }
    vector<int> sortedArray(arr.size(), 0);
    vector<int> count(maxValue-minValue+1, 0);

    for(int i=0; i<arr.size(); i++){ //计数
        count[arr[i]-minValue]++;
    }
    for(int i=1; i<count.size(); i++){ //累加
        count[i]+=count[i-1];
    }

    for (int k = arr.size()-1; k >=0; k--) { //反向填充，可以保证稳定性
        sortedArray[count[arr[k]-minValue]-1] = arr[k];
        count[arr[k]-minValue]--;
    }
    return sortedArray;
}

分析

  • 时间复杂度：O(n+k)，k就是maxValue-minValue+1。
  • 空间复杂度：O(n+k)，与时间复杂度相同。
  • 稳定性：稳定，见代码。

桶排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BucketSort(vector<int>& arr) {
    vector<vector<int>> buckets(10); //这里假设有10个桶 
    //基本思想是将数组中的元素分配到几个桶里，然后对每个桶分别排序（可能用到其它算法）
    //如果桶的数量等于数组元素的数量，就变成了计数排序
    for(int i=0; i<arr.size(); i++){
        buckets[a[i] / 10].push_back(a[i]); //例如，0~9放到buckets[0]里，11~19放到buckets[1]里……
    }
    for(int i=0; i<10; i++){
        sort(buckets[i].begin(), buckets[i].end()); //桶内排序
    }
    int index=0;
    for(int i=0; i<10; i++){
        for(int j=0; j<buckets[i].size(); j++){
            arr[index++]=buckets[i][j];
        }
    }
}

分析

  • 时间复杂度：如果要排序的数据有n个，我们把它们分在m个桶中，这样每个桶里的数据就是k = n/m。每个桶内排序（假设用快排）的时间复杂度就为O(k*logk)。m个桶就是
    m*O(klogk)=m*O((n/m)*log(n/m))=O(n*log(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个较小的常数，所以时间复杂度接近O(n)。但是如果运气不好，所有的元素都到了一个桶了，那么它的时间复杂度就退化成 O(nlogn) 了。
  • 空间复杂度：O(n+m)，其中n为待排序元素的个数，m为桶的数量。
  • 稳定性：取决于桶内排序使用的算法。

基数排序

代码实现

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 RadixSort(vector<int>& arr) 
{
    int bit = maxbit(arr);
    vector<int> tmp(arr.size());
    vector<int> count(10); //0-9计数器
    int i, j, k;
    int radix = 1;
    for (i = 1; i <= bit; i++) //进行bit次排序
    {
        for (j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for (j = 0; j < arr.size(); j++)
        {
            k = (arr[j] / radix) % 10; 
            count[k]++;
        }
        for (j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; 

        for (j = arr.size() - 1; j >= 0; j--) //和前面计数排序的原理相同
        {
            k = (arr[j] / radix) % 10;
            tmp[count[k] - 1] = arr[j];
            count[k]--;
        }

        for (j = 0; j < arr.size(); j++) 
            arr[j] = tmp[j];
        radix = radix * 10;
    }
}

分析

  • 时间复杂度：基数排序的时间复杂度是O(k*n),其中n是排序的元素个数，k是元素中最大元素的位数。
  • 空间复杂度：O(n+m)，n为tmp数组的长度，m为count数组的长度。
  • 稳定性：是稳定的，原因同计数排序。

希尔排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(vector<int>& arr) {
    for (int gap = arr.size() / 2; gap > 0; gap /= 2) { //最初的gap是n/2，不断对步长折半
        for (int i = gap; i < arr.size(); i++) { //每一轮循环，排序下标为i, i+gap, i+2*gap...的元素
            int temp = arr[i];
            int j;
            //这里用的是插入排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }

            arr[j] = temp;
        }
    }
}

分析

  • 时间复杂度：和步长序列有关，以上代码展示序列的时间复杂度为O(n^(1.3-2))。
  • 空间复杂度：原地排序，没有额外空间消耗。
  • 稳定性：将数据分组并存在元素的交换，所以不稳定。

堆排序

代码实现

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
void Heapify(vector<int> &arr, int n, int i){
    int smallest=i; //这里维护的是一个小顶堆
    int left=2*i+1, right=2*i+2;
    if(left<n && arr[left]<arr[smallest]){
        smallest=left;
    }
    if(right<n && arr[right]<arr[smallest]){
        smallest=right;
    }
    if(smallest!=i){
        swap(arr[i], arr[smallest]);
        heapify(arr, n, smallest);
    }
}

void HeapSort(vector<int> &arr, int len){
    for(int i=len/2-1; i>=0; i--){
        Heapify(arr, len, i);
    }
    for(int i=len-1; i>0; i--){
        swap(arr[0], arr[i]);
        Heapify(arr, i, 0);
    }
    reverse(arr.begin(), arr.end());
}

分析

  • 时间复杂度：在所有情况下均为O(nlogn)。
  • 空间复杂度：没有用到额外空间。
  • 稳定性：堆排序是不稳定的，因为堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。