CTF of Z2BNS
0%

十大排序算法详解

发表于 更新于 分类于
| 阅读次数： |
Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

十大排序算法可以说是每个程序员都必须得掌握的了

术语铺垫

有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小。

快速排序（Quicksort）

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

quickSort

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
//快速排序
void quickSort(int arr[],int left, int right){
    if(left>=right){
        return;
    }
    int pivot=arr[left];
    int l=left+1;
    int r=right;
    int tmp;
    while(true){
        while(l<=r && arr[l]<=pivot){
                    ++l;
        }
        while(l<=r && arr[r]>=pivot){
            --r;
        }
        if(l>=r){
            break;
        }
        //交换
        tmp=arr[l];
        arr[l]=arr[r];
        arr[r]=tmp;
    }

    arr[left]=arr[r];
    arr[r]=pivot;
    quickSort(arr,left,r-1);
    quickSort(arr,r+1,right);
}
归并排序（Merge Sort)

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。

mergeSort

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 mergeSort(int arr[],int tmp[],int left,int right){
    if(left<right){
        int center=(left+right)/2;
        //左边数组排序
        mergeSort(arr,tmp,left,center);
        //右边数组排序
        mergeSort(arr,tmp,center+1,right);
        //合并
        int i=left;
        int j=center+1;
        for(int k=left;k<=right;++k){
            if(i>center){
                tmp[k]=arr[j++];
            }else if(j>right){
                tmp[k]=arr[i++];
            }else if(arr[i]<=arr[j]){
                tmp[k]=arr[i++];
            }else{
                tmp[k]=arr[j++];
            }
        }
        for(int k=0;k<=right;++k){
            arr[k]=tmp[k];
        }
    }
}

插入排序

我们在玩打牌的时候，你是怎么整理那些牌的呢？一种简单的方法就是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候，为了要插入元素，我们需要腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序。

过程简单描述：

1、从数组第2个元素开始抽取元素。

2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。

3、继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。

insertSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//插入排序
void insertionSort(vector<int>& arr){
    int n=arr.size();
    int j=0;
    int tmp;
    for(int i=1;i<n;++i){
        j=i-1;
        tmp=arr[i];
        while(j>=0&&arr[j]>tmp){
            arr[j+1]=arr[j];
            --j;
        }
        arr[j+1]=tmp;
    }

}
冒泡排序

把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置….

我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。

除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

bubbleSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//冒泡排序
void bubbleSort(vector<int>& arr){
    int n=arr.size();
    int tmp;
    //n-1趟
    for(int i=0;i<n-1;++i){
        //每趟比较n-i-1次
        for(int j=0;j<n-1-i;++j){
            if(arr[j]>arr[j+1]){
                //稳定排序，只有前者和后者相等时不交换顺序
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }
}
选择排序（Selection Sort）

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//选择排序
void selectSort(vector<int>& arr){
    int n=arr.size();
    int minIndex;
    //从无序区间不断挑选出最小值，挑选n-1次（最后一个元素不用挑）
    for(int i=0;i<n-1;++i){
        //i下标左边是已经排好序的元素，右边（包括i）是无序区间
        //最小值下标默认为无序区间第一个元素下标
        minIndex=i;
        for(int j=i+1;j<n;++j){
            if(arr[j]<arr[minIndex]){
                //更新最小值下标
                minIndex=j;
            }
        }
        swap(arr[minIndex],arr[i]);//交换最小值和无序区间的第一个元素
    }
}
希尔排序

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要n-1次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为h的元素有序，则刚开始h的大小可以是h=n/2，接着让h=n/4,让h一直缩小，当h=1时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

shellSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//希尔排序
void shellSort(vector<int>& arr){
    int n=arr.size();
    //进行分组，最开始的增量(gap)为数组长度的一半
    for(int gap=n/2;gap>0;gap/=2){
            //对各个分组进行插入排序
            for(int i=gap;i<n;++i){
                //将arr[i]插入到分组的正确位置上
                int inserted=arr[i];
                int j=i-gap;
                while(j>=0 && inserted<arr[j]){
                    arr[j+gap]=arr[j];
                    j-=gap;
                }
                arr[j+gap]=inserted;
            }
    }
}
堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。

堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换…如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

heapSort

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
//堆排序
//下沉操作
//arr
void downAdjust(vector<int>& arr,int parent,int length){
    int tmp=arr[parent];
    int child=2*parent+1;
    while(child<length){
        //如果右孩子节点比左孩子小，则定位到右孩子
        if(child+1<length && arr[child]>arr[child+1]){
            ++child;
        }
        //若父节点比孩子节点小或等于，则下沉结束
        if(tmp<=arr[child]){
            break;
        }
        //单向赋值
        arr[parent]=arr[child];
        parent=child;
        child=2*parent+1;
    }
    arr[parent]=tmp;
}
void heapSort(vector<int>& arr,int length){
    //构建二叉堆
    for(int i=(length-2)/2;i>=0;--i){
        downAdjust(arr,i,length);
    }
    //进行堆排序
    for(int i=length-1;i>=1;--i){
        //将堆顶的元素与最后一个元素交换
        int tmp=arr[i];
        arr[i]=arr[0];
        arr[0]=tmp;
        //下沉调整
        downAdjust(arr,0,i);
    }
}
计数排序

计数排序是一种适合于最大值和最小值的差值不是很大的排序。

基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如temp[i]=m,表示元素i一共出现了m次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来数据是有序的。

countSort

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
//8、计数排序
void countSort(vector<int>& arr){
    int n=arr.size();
    int max_num=arr[0];
    int min_num=arr[0];
    //寻找数组的最大值
    for(int i=1;i<n;++i){
        if(max_num<arr[i]){
            max_num=arr[i];
        }
        if(min_num>arr[i]){
            min_num=arr[i];
        }
    }
    //创建一个大小为max_num-min_num+1的临时数组
    int d=max_num-min_num+1;
    vector<int> tmp(d,0);
    //统计元素出现的次数
    for(int i=0;i<n;++i){
        ++tmp[arr[i]-min_num];
    }
    int k=0;
    //把临时数组统计好的数据汇总到原数组
    for(int i=0;i<d;++i){
        for(int j=tmp[i];j>0;--j){
            arr[k++]=i+min_num;
        }
    }
}
桶排序

桶排序就是把最大值和最小值之间的数进行瓜分，例如分成10个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。

之后每个桶里面的数据就是有序的了，我们再进行合并汇总。

bucketSort

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
//桶排序
void bucketSort(vector<int>& arr){
    int n=arr.size();
    int max_num=arr[0];
    int min_num=arr[0];
    //寻找数组的最大值和最小值
    for(int i=0;i<n;++i){
        if(max_num<arr[i]){
            max_num=arr[i];
        }
        if(min_num>arr[i]){
            min_num=arr[i];
        }
    }
    //大小为min_num的偏移值
    int d=max_num-min_num;
    //创建
    int bucketNum=n;
    vector<vector<int>> bucketList(bucketNum);
    //遍历原数组，将每个元素放入桶中
    for(int i=0;i<n;++i){
        bucketList[(arr[i]-min_num)*(bucketNum-1)/d].emplace_back(arr[i]-min_num);
    }
    //对桶内的元素进行排序
    for(int i=0;i<bucketNum;++i){
        sort(bucketList[i].begin(),bucketList[i].end());
    }
    //把每个桶排序好的数据进行合并汇总放回原数组
    int k=0;
    for(auto i:bucketList){
        for(int j:i){
            arr[k++]=j+min_num;
        }
    }
}
基数排序

基数排序的排序思路是这样的：先以个位数的大小来对数据进行排序，接着以十位数的大小来对数进行排序，接着以百位数的大小…

排到最后，就是一组有序的元素了。不过，她在以某位数进行排序的时候，是用“桶”来排序的。

由于某位数（个位/十位…，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了。

radioSort

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
//基数排序
void radioSort(vector<int>& arr){
    int n=arr.size();
    int max_num=arr[0];
    for(int i=0;i<n;++i){
        max_num=max(max_num,arr[i]);
    }
    //计算最大值是几位数
    int num=1;
    while(max_num/10>0){
        ++num;
        max_num/=10;
    }
    //创建10个桶
    vector<vector<int>> bucketList(10);
    //进行每一趟的排序，从个位数开始排
    for(int i=1;i<=num;++i){
        for(int j=0;j<n;++j){
            int radio=arr[j]/(int)pow(10,(i-1))%10;
            //放到对应桶里
            bucketList[radio].emplace_back(arr[j]);
        }
        //合并放回原数组
        int k=0;
        for(auto j:bucketList){
            for(int t:j){
                arr[k++]=t;
            }
            //取出来合并了之后把桶数据清空
            j.clear();
        }
    }
}
10大排序算法的性质

sort

参考

【必学十大经典排序算法，看这篇就够了(附完整代码/动图/优质文章)】

------------- THE END! THANKS! -------------