十大排序算法详解
秋名山码民 人气:0前言
兄弟们，应上篇数据结构的各位要求，今天我开始工作了，开始肝算法，剑指offer还在路上，我真想开车去接它，奈何码神没有驾照的开车，算了，弄排序算法吧，有点长，耐心看啊，原创不易，你们懂的，先上一张图
可以看出排序算法，还是比较多的，算了，不多说了，你我肝完就是出门自带4年实习经验的！
交集排序
冒泡
冒泡我一般也将它称为枚举就是把所有都走一遍嘛，效率比较低，一般在算法竞赛中如果实在没有比较好的，可以用，那就先讲一个简单的枚举吧！
枚举字典序
首先可能有的同学不知道什么是字典序，请看：
（1，2，3），（1，3，2）…这就是字典序的体现，官方解释是这样的：
字典排序（lexicographical order）是一种对于随机变量形成序列的排序方法。其方法是，按照字母顺序，或者数字小大顺序，由小到大的形成序列。
比如说有一个随机变量X包含{1 2 3}三个数值。
其字典排序就是{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}
如果是字母：先比较第一个字符i和b，b<i，b是第2个，i是第9个2<9于是baray<ilove如果第一位相同，就比较第二位，
例如：abcdd<abcde aaaay<aaaaz如果其中之一是另一个的前缀，则短的那个排前面：aaa
下面用代码实现一下1-n的排列：
//冒泡排序，我也将它称为枚举
#include<iostream>
#include<cstdio>
using namespace std;
void print(int n, int *a, int cur)
{
if (cur == n)//递归边界
{
for (int i = 0; i < n; i++)
{
printf("%d", a[i]);
}
printf("\n");
}
else for (int i = 1; i <= n; i++)
{
int OK = 1;
for (int j = 0; j < cur; j++)
{
if (a[j] == i)//判断i是否出现过
OK = 0;
if (OK)//i没有出现过下一个
{
a[cur] = i;
print(n, a, cur + 1);//递归
}
}
}
}
int main()
{
}下面我们来看一下正宗的冒泡排序，总体思想是：俩俩比较，如果反序交换，直到没有反序的记录为止，代码实现比较简单，是俩个for循环的嵌套
#include<iostream>
#include<algorithm>//调用算法库，使用交换函数swap
#include<cstdio>
using namespace std;
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
cin >> a[i];
}
for (int i = 0; i < 10; i++)
{
for (int j = i + 1; j < 10; j++)
{
if (a[i] < a[j])
swap(a[i], a[j]);
}
}
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}
总体来说比较简单，但是耗时，耗内存，反正就是不好，来优化一下，为什么不好？归根结底还是做了许多重复的运算，大量的比较，
总体思路是这样的：再某一次比较后，发现所有的数据都变成了顺序，直接退出循环，不再继续循环
//将for改为
bool flag = true;
for (int i = 0; i < 10 && flag; i++)
{
flag = false;
for (int j = 10 - 1; j >= i; j--)
{
if (a[j] > a[i])
{
swap(a[j], a[j + 1]);
flag = true;
}
}
}算法复杂度：俩个for，就是O（n^2)了，有点大
简单
选择排序
先来和冒泡排序比较一下，他俩的主要区别就是冒泡排序的数据在不断的交换，而快速排序先交换数据的别名，再交换本身。打个比喻就是，一个是幻想天上掉馅饼，背水一战，的炒股短线选手，而另一个则是看中时机的炒股老手，俗称股神。
好了，比较也比较完了，我们来看简单的代码实现吧
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
cin >> a[i];
}
for (int i = 0; i < 10; i++)
{
int min = i;
for (int j = i + 1; j < 10; j++)
{
if (a[min] > a[j])
min = j;//交换下标位置
}
if (i != min)
swap(a[i], a[min]);
}
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}如果来分析算法复杂度的话，你会惊讶的发现时间复杂度仍旧是O（n^2)，但是我要说的是它仍旧优于冒泡排序，why？
冒泡排序和选择排序是排序算法中比较简单和容易实现的算法。冒泡排序的思想为：每一次排序过程，通过相邻元素的交换，将当前没有排好序中的最大（小）移到数组的最右（左）端。而选择排序的思想也很直观：每一次排序过程，我们获取当前没有排好序中的最大（小）的元素和数组最右（左）端的元素交换，循环这个过程即可实现对整个数组排序。
选择排序的平均时间复杂度比冒泡排序的稍低:
同样数据的情况下，2种算法的循环次数是一样的，但选择排序只有0到1次交换，而冒泡排序只有0到n次交换
快速排序
和冒泡排序相似，但是优于冒泡，总体是一个分治的思想，交换轴点元素
- 划分：将数组中的元素都重排分成左右俩部分，使得左边都小于等于右边的任意元素
- 递归求解：把左右分别进行排序
- 合并：这时你会发现已经排列好了
还是排列一串数字，进行代码实现：
#include<iostream>
using namespace std;
void quickSort(int *arr,int begin,int end)
{
//begin为左，end为右
//如果区间不只一个数
if(begin < end)
{
int temp = arr[begin]; //将区间的第一个数作为基准数
int i = begin; //从左到右进行查找时的“指针”，指示当前左位置
int j = end; //从右到左进行查找时的“指针”，指示当前右位置
//不重复遍历
while(i < j)
{
//当右边的数大于基准数时，略过，继续向左查找
//不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
while(i<j && arr[j] > temp)
j--;
//将右边小于等于基准元素的数填入右边相应位置
arr[i] = arr[j];
//当左边的数小于等于基准数时，略过，继续向右查找
//(重复的基准元素集合到左区间)
//不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
while(i<j && arr[i] <= temp)
i++;
//将左边大于基准元素的数填入左边相应位置
arr[j] = arr[i];
}
//将基准元素填入相应位置
arr[i] = temp;
//此时的i即为基准元素的位置
//对基准元素的左边子区间进行相似的快速排序
quickSort(arr,begin,i-1);
//对基准元素的右边子区间进行相似的快速排序
quickSort(arr,i+1,end);
}
//如果区间只有一个数，则返回
else
return;
}
int main()
{
int num[12] = {23,45,17,11,13,89,72,26,3,17,11,13};
int n = 12;
quickSort(num,0,n-1);
cout << "排序后的数组为：" << endl;
for(int i=0;i<n;i++)
cout << num[i] << ' ';
cout << endl;
return 0;
}算一下复杂度吧，最坏O（n^2），平均O（nlogn）几乎没有最坏的情况发生，所以效率还是比较高的，想一想如果就只要最大的值怎么弄？
#include<iostream>
using namespace std;
int Partition(int *a, int i, int j)
{
int tmp = a[j];
int index = i;
if (i < j)
{
for (int k = i; k < j; k++) {
if (a[k] >= tmp) {
swap(a[index++], a[k]);
}
}
swap(a[index], a[j]);
return index;
}
}
int Search(int a[], int i, int j, int k)
{
int m = Partition(a, i, j);
if (k == m - i + 1) return a[m];
else if (k < m - i + 1)
{
return Search(a, i, m - 1, k);
}
//后半段
else
{
//核心后半段：再找第 k-(m-i+1)大的数就行
return Search(a, m + 1, j, k - (m - i + 1));
}
}
int main()
{
int a[7] = { 8,7,6,1,2,3,4 };
int k = 3;
cout << Search(a, 2, 6, k);
}插入排序
直接插入排序
话说，码神最近在玩斗地主，你们说手机斗地主和真人斗地主最大的区别，或者是说好处是什么？我感觉就是在手机上不用插牌了，省时间，这利用的就是插入排序的原理，可以说是“斗地主排序”
基本操作：将一个记录插入到已经排好的有序表中，从而得到一个新的，记录数据+1的有序表
基操，看代码：
void insertionSort(int *arr, int len) {
if (len<2) {
return ;
}
for (int i=1; i<len; i++) {
int insertValue = arr[i];//暂存需要插入元素
int j = i-1;
//从右向左比较元素
for (; j>=0 && insertValue<array[j]; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = insertValue;
}
}老规矩，分析时间复杂度，最好的情况是顺序都是排列好的，此时只需要比较，时间复杂度为O（n），最坏的情况为O（n^2),平均下来是n ^ 2/4，所以平均时间复杂度也是O（n ^ 2).
希尔排序
如果说谁是第一个将排序算法复杂度突破O（n^2)的，那么我想希尔是第一个，可以说希尔排序是对插入排序的改进，区别在于，希尔排序可以说是一个不断分组的排序
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
实现如下：
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap>1)
{
//每次对gap折半操作
gap = gap / 2;
//单趟排序
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tem = arr[end + gap];
while (end >= 0)
{
if (tem < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tem;
}
}
}时间复杂度，牛逼的人们，通过大量的计算发现是O（n^3/2)，小于O
（n^2)，由于是跳跃式的排序所以不是稳定排序
选择排序
简单选择排序
可参考上面
堆排序
何为堆，如果已经学过堆的话，就是那个堆，与栈相对的堆，
基本思路：将代排的序列构造成一个大堆，此时，整个序列的最大值就是堆顶的根结点，将它移走，也就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素的次最大值，如此递归反复就会得到一个有序序列
varlen; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for(vari = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆调整
varleft = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if(left < len && arr[left] > arr[largest]) {
largest = left;
}
if(right < len && arr[right] > arr[largest]) {
largest = right;
}
if(largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
vartemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for(vari = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}时间可以说是主要耗在了初始建堆和在重建堆的反复筛选上
1.构造堆：O（n）
2.重建堆：完全二叉树：数据结构，详解时间复杂度为O(nlogn)
又因为堆排序对原始记录的排序状态并不敏感，因此它无论是好是坏，时间复杂度都为O（nlogn)，同希尔排序，都为不稳定性的排序
归并排序
完全二叉树，是一棵神奇的树，可以说归并排序是完全体现了完全二叉树的性质
二路
若将两个有序表合并成一个有序表，称为2-路归并。
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
#include<iostream>
using namespace std;
void Merge(int[], int, int[], int, int, int)
void MergeSort(int numbers[], int length, int temp[], int begin, int end)
{
//1. 同样判断传入的参数是否有效
if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
throw new exception("Invalid input.");
//2. 作为递归的结束条件，开始下标和结束下标相等时，说明子序列中只有一个元素，看作有序的
if (end - begin == 0)
return;
//3. 定义中间变量，将数组分半【如果有7个元素，下标0-6，则middle=3，数组分为长度为4和3的两段】
int middle = ((end - begin) / 2 ) + begin;
//4. 递归，先递归左半边，再递归右半边，将左右子序列不断分为长度为1的子序列才停止递归
MergeSort(numbers, length, temp, begin, middle);
MergeSort(numbers, length, temp, middle + 1, end);
//5. 再慢慢归并
Merge(numbers, length, temp, begin, end, middle);
}
void Merge(int numbers[], int length, int temp[], int begin, int end, int middle)
{
//1. 判断是否有不符合要求的参数传入，有则抛出错误
if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
throw new exception("Invalid input.");
//2. 将原序列从中分开
int leftIndex = begin; //左边序列的开始（左边序列的结尾是middle）
int rightIndex = middle + 1;//右边序列的开始（右边序列的结尾是end）
int tempIndex = begin; //辅助数组的下标
//3. 当左右子序列尚未到头时，循环
while (leftIndex <= middle && rightIndex <= end)
{
//4. 两两对比判断，谁大谁就放入辅助数组，同时指针后移
if (numbers[leftIndex] < numbers[rightIndex])
temp[tempIndex] = numbers[leftIndex++];
else
temp[tempIndex] = numbers[rightIndex++];
//5. 辅助数组下标++
++tempIndex;
}
//6. 当左边或右边子序列尚未到头时，直接放入辅助数组
while (leftIndex <= middle)
temp[tempIndex++] = numbers[leftIndex++];
while (rightIndex <= end)
temp[tempIndex++] = numbers[rightIndex++];
//7. 再将辅助数组中已经有序的元素覆盖掉原数组中无序的元素，使原数组变成部分有序
for (int i = begin; i <= end; ++i)
numbers[i] = temp[i];
}
int main(int arvc, char* argv[])
{
const int length = 9;
int nums[length] = { 18, 7, 23, 3, 9, 32, 10 , 99, 0};
int *temp = new int[length];
MergeSort(nums, length, temp, 0, 8);
for (int i = 0; i < length; i++)
cout << nums[i] << " ";
delete[] temp;
temp = nullptr;
cout << endl;
return 0;
}
多路
同理，将多个有序表合并，称为多路归并，和二路归并几乎一样，就不赘述了，
非比较类
计数排序
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
#include <iostream>
using namespace std;
const int MAXN = 1000;
int arr[MAXN];
void counting_sort(int n)
{
int min_value = 0x3f3f3f3f, max_value = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] > max_value)
max_value = arr[i];
if (arr[i] < min_value)
min_value = arr[i];
}
int len = max_value - min_value + 1;
int* bucket = new int[len]();
for (int i = 0; i < n; i++)
{
bucket[arr[i] - min_value]++;
}
for (int i = 0, j = 0; i < len; i++)
{
while (bucket[i] != 0)
{
arr[j++] = i + min_value;
bucket[i]--;
}
}
delete bucket;
}
int main()
{
int n;
cout << "请输入数组中元素的个数：";
cin >> n;
cout << "请输入元素: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "排序前：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
counting_sort(n);
cout << "排序后：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
const int BUCKET_SIZE = 10;//默认每个桶的范围
int arr[MAXN];
void insert_sort(vector<int> &v){
int len=v.size(),temp,i,j;
for(i=1;i<len;i++){
temp = v[i];
for(j=i;j>0 && v[j-1]>temp;j--){
v[j]=v[j-1];
}
v[j]=temp;
}
}
void bucket_sort(int n){
int min_value = 0x3f3f3f3f, max_value = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] > max_value)
max_value = arr[i];//获取输入数据的最大值
if (arr[i] < min_value)
min_value = arr[i];//获取输入数据的最小值
}
//桶的初始化
int len = (max_value-min_value)/BUCKET_SIZE+1;
vector<int> bucket[len];
//将数据分配到桶
for(int i=0;i<n;i++){
bucket[(arr[i]-min_value)/BUCKET_SIZE].push_back(arr[i]);
}
for(int i=0,j=0;i<len;i++){
//这里建议使用插入排序或者计数排序。当然也可以使用堆排序，快速排序等等
insert_sort(bucket[i]);
for(auto x:bucket[i]){
arr[j++]=x;
}
}
}
int main(){
int n;
cout << "请输入数组中元素的个数：";
cin >> n;
cout << "请输入元素: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "排序前：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
bucket_sort(n);
cout << "排序后：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。是一个用空间换时间的算法
基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成r数组；
- 对r进行计数排序（利用计数排序适用于小范围数的特点）；
#include <iostream>
#include <queue>
using namespace std;
using namespace std;
const int MAXN = 1000;
int arr[MAXN];
queue<int> q[10];
void radix_sort(int n)
{
//获取最大值的位数
int max_value = 0;
for (int i = 0; i < n; i++)
{
if (max_value < arr[i])
max_value = arr[i];
}
int max_digit = 0;
while (max_value)
{
max_digit++;
max_value /= 10;
}
//开始排序
int mod = 10, dev = 1;
for (int i = 0; i < max_digit; i++, mod *= 10, dev *= 10)
{
for (int j = 0; j < n; j++)
{
int ix = arr[j] % mod / dev;
q[ix].push(arr[j]);
}
int pos = 0;
for (int j = 0; j < 10; j++)
{
while (!q[j].empty())
{
arr[pos++] = q[j].front();
q[j].pop();
}
}
}
}
int main()
{
int n;
cout << "请输入数组中元素的个数：";
cin >> n;
cout << "请输入元素: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "排序前：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
radix_sort(n);
cout << "排序后：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。
最后
加载全部内容