十大经典排序算法C++版

对排序的一些术语进行说明。

  • 稳定：如果在原数组中，a在b之前且a=b，排序后a也要在b之前。
  • 不稳定：如果子啊原数组中国，a在b之前且a=b，排序后a可能会出现在b之后。
  • 内排序：所有的排序操作都在内存中完成。
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度： 一个算法执行所耗费的时间。
  • 空间复杂度：运行完一个程序所需内存的大小。

具体原理：超详细十大经典排序算法总结

1、冒泡排序

两两比较，将大数逐渐交换到数列到最后方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> bubble_sort(vector<int>array){
    int n = array.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n-i-1; j++)
        {
            if(array[j]>array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
    return array;
}

算法分析

  • 最佳情况：T(n) = O(n) 使用一个flag，当遍历一遍都不交换时，直接返回
  • 最差情况：T(n) = O(n2)
  • 平均情况：T(n) = O(n2)
  • 稳定

2、选择排序

从左往右，依次寻找当前数列中最小的数字，并交换到最前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> sort(vector<int>array){
    int n = array.size();
    for (int i = 0; i < n; i++)
    {
        int minIndex = i;
        for (int j = i; j < n; j++)
        {
            if(array[j]<array[minIndex])    minIndex = j;
        }
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
    return array;
}
  • 最佳情况：T(n) = O(n2)
  • 最差情况：T(n) = O(n2)
  • 平均情况：T(n) = O(n2)
  • 不稳定

3、插入排序

从左往右，依次将本数字插入到第一个小于它的数字后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> sort(vector<int>array){
    int n = array.size();
    for (int i = 1; i < n; i++)
    {
        int current = array[i];
        int j = i-1;
        while(current<array[j]&&j>=0){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = current;
    }
    return array;
}
  • 最佳情况：T(n) = O(n)
  • 最坏情况：T(n) = O(n2)
  • 平均情况：T(n) = O(n2)
  • 稳定

4、希尔排序

相对于插入排序，希尔排序通过分组的方式将排序的范围拉的更宽，使靠后的小数字可以更快地被换到前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> sort(vector<int>array){
    int n = array.size();
    int gap = n/2;
    int temp,preIndex;
    while(gap>0){
        for(int i = gap;i<n;i++){
            preIndex = i-gap;
            temp = array[i];
            while(preIndex>=0&&array[preIndex]>temp){
                array[preIndex+gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex+gap] = temp;
        }
        gap /= 2;
    }
    return array;
}
  • 最佳情况：$T(n) = O(n)$
  • 最坏情况：$T(n) = O(log_2n)$
  • 平均情况：$T(n) = O(log_2n)$
  • 不稳定

5、归并排序

使用分治算法，将待排序的序列二分，然后再进行合并。

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
vector<int> merge(vector<int>left, vector<int>right){
    int l = left.size();
    int r = right.size();
    vector<int>res;
    for(int index = 0, i = 0, j = 0; index<l+r; index++){
        if(i>=l){
            res.push_back(right[j++]);
        }else if(j>=r){
            res.push_back(left[i++]);
        }else if(left[i]<right[j]){
            res.push_back(left[i++]);
        }else{
            res.push_back(right[j++]);
        }
    }
    return res;
}

vector<int> sort(vector<int>array){
    int n = array.size();
    if(n<2) return array;
    int mid = n/2;
    vector<int>left(array.begin(),array.begin()+mid);
    vector<int>right(array.begin()+mid,array.end());
    return merge(sort(left),sort(right));
}
  • 最佳情况：$T(n) = O(log_2n)$
  • 最坏情况：$T(n) = O(log_2n)$
  • 平均情况：$T(n) = O(log_2n)$
  • 不稳定

6、快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partition(vector<int>&array, int low, int high){
    int temp = array[low];
    while(low<high){
        while(array[high]>temp&&low<high)   high--;
        array[low] = array[high];
        while(array[low]<temp&&low<high)    low++;
        array[high] = array[low];
    }
    array[low] = temp;
    return low;
}

void sort(vector<int>&array, int low, int high){
    if(low<high){
    int index = partition(array,low,high);
    sort(array,low,index-1);
    sort(array,index+1,high);
    }
}

分治的思想，设置一个“基准”数据，将所有大于该数据的都放到后面，所有小于该数据的都放到前面，再分别对前后数据进行分治操作。

  • 最佳情况：$T(n) = O(log_2n)$
  • 最坏情况：$T(n) = O(log_2n)$
  • 平均情况：$T(n) = O(n^2)$

7、堆排序

构建最大堆（顶点数据比子数据大），再将顶点交换到最后即可。

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
void adjustHeap(vector<int>&array,int i,int len){
    int maxIndex = i;
    if(2*i+1<len&&array[2*i+1]>array[maxIndex])    maxIndex = 2*i+1;
    if(2*i+2<len&&array[2*i+2]>array[maxIndex])    maxIndex = 2*i+2;
    if(maxIndex!=i){
        int temp = array[i];
        array[i] = array[maxIndex];
        array[maxIndex] = temp;
        adjustHeap(array,i,len-1);
    }
}


void sort(vector<int>&array, int low, int high){
    int len = array.size();
    if(len<2)return;
    //构造初始堆
    for(int i = len/2-1;i>=0;i--){
        adjustHeap(array,i,len);
    }
    //将最大值交换到最后，继续调整
    for(int i = len-1;i>0;i--){
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        adjustHeap(array,0,i);
    }
}
  • 最佳情况：$T(n) = O(log_2n)$
  • 最差情况：$T(n) = O(log_2n)$
  • 平均情况：$T(n) = O(log_2n)$

8、计数排序

使用一个额外的数组来存储数组中每一个数字出现的次数。

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
void sort(vector<int>&array){
    int n = array.size();
    if(n<2) return;
    int maxValue = array[0];
    int minValue = array[0];
    for(int i = 1;i<n;i++){
        maxValue = max(maxValue,array[i]);
        minValue = min(minValue,array[i]);
    }
  
    int len = maxValue-minValue+1;

    //构建大小为10的桶
    vector<int>bucket(len);
    //向桶中放数据
    for(int i = 0;i<len;i++){
        int num = array[i]-minValue;
        bucket[num]++;
    }
    //将桶中的数据放回原数据
    int index = 0;
    for(int i = 0;i<len;i++){
        while(bucket[i]!=0){
            bucket[i]--;
            array[index] = i+minValue;
            index++;
        }
    }
}

9、桶排序

使用桶进行数据的存储，其中桶的长度和数量依照数组的范围自动确定。

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
void sort(vector<int>&array){
    int n = array.size();
    if(n<2) return;
    int maxValue = array[0];
    int minValue = array[0];
    for(int i = 1;i<n;i++){
        maxValue = max(maxValue,array[i]);
        minValue = min(minValue,array[i]);
    }
    //构建桶
    int len = (maxValue-minValue)/n+1;
    vector<vector<int> >bucket(len);
    //将数据填入桶中
    for(int i = 0;i<n;i++){
        int num = (array[i]-minValue)/n;
        bucket[num].push_back(array[i]);
    }
    for(int i = 0;i<len;i++){
        sort(bucket[i].begin(),bucket[i].end());
    }
    //将桶中的数据放回原数据
    int index = 0;
    for(int i = 0;i<len;i++){
        for(int j=0;j<bucket[i].size();j++){
            array[index] = bucket[i][j];
            index++;
        }
    }
}

10、基数排序

将桶的大小固定为10，再对每个数字按照其个位、十位等的顺序依次入桶出桶。

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
void sort(vector<int>&array){
    int n = array.size();
    if(n<2) return;
    int maxValue = array[0];
    for(int i = 1;i<n;i++){
        maxValue = max(maxValue,array[i]);
    }
  
    int len = 0;
    while(maxValue!=0){
        maxValue/=10;
        len++;
    }
    //构建大小为10的桶
    vector<vector<int> >bucket(10);
    //向桶中放数据
    int mod = 10, div = 1;
    for(int i = 0;i<len;i++){
        for(int j = 0;j<n;j++){
            int num = (array[j]%mod)/div;
            bucket[num].push_back(array[j]);
        }
    //将桶中的数据放回原数据
    int index = 0;
        for(int i = 0;i<10;i++){
            for(int j=0;j<bucket[i].size();j++){
                array[index] = bucket[i][j];
                index++;
            }
        }
    }
}