常见排序算法

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。
常见的排序算法：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序和归并排序。
直接插入排序，冒泡排序和归并排序是稳定的，其他的排序是不稳定的。
归并排序可做内部排序也可做外部排序。
排序的稳定性判断：如果有两个相同的值（我们通过字母标注其不同a,b），在排序之前a在前,b在后，当数组有序时,a还是在前,b还是在后这就表示这个排序是稳定的，否则就是不稳定的。

冒泡排序

冒泡排序的核心思想：两两比较，如果两者不满足顺序要求就进行交换，每趟都会排好一个数，每趟都需要比较不同的次数。所以其代码实现如下（通过设置了一个flag标志来优化冒泡排序）。冒泡排序的时间复杂度为O(N^2),空间复杂度为O(1)，并且是稳定的排序。

冒泡排序算法的示意如下：

冒泡排序的代码实现如下：

//冒泡排序
void bubblesort(int* arr, int n)
{//趟数for (int i = 0; i < n - 1; i++){//假设每趟都是有序的int flag = 1;//次数--每趟排好一个数的次数for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){swap(&arr[j], &arr[j + 1]);flag = 0;//进入到这表示还是无序的还需要继续，将flag置0}}if (flag == 1)//如果flag==1表示有序退出循坏{break;}}
}

直接插入排序

直接插入排序的的思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。插入排序的思想跟玩扑克牌时进行插牌操作时类似的。插入排序的时间复杂度也是O(N^2)，空间复杂度为O(1),并且也是稳定的排序。

插入排徐的示意图如下：

插入排序代码实现

void insertsort(int* arr, int n)
{for (int i = 0; i < n - 1; i++)//插入n-1趟{//每趟插入的算法int end = i;//end表示前面有序数组中的最后一个元素位置int tmp = arr[end + 1];//有序数组后一个数据while (end >= 0)//当end>=0就继续执行插入，不满足插入条件也退出循环{if (arr[end] > tmp)//如果有序数组中最后一个end位置的元素比无序部分end+1大就将end位置的元素往后挪{arr[end + 1] = arr[end];end--;}else{break;//当arr[end] <= tmp就退出循环}}arr[end + 1] = tmp;//将这个数据写入end+1这个位置}
}

希尔排序

希尔排序的实现是在插入排序的基础上进行一步改进所实现的。通过gap进行预排序，预排序是待排序数组接近有序。排序的主要思路是通过gap增量序列{n, n/3, n/9, …, 1}。根据当前的增量gap将数列分成多个子序列，每个子序列中的元素间隔为gap。通过循环遍历每个子序列的第一个元素，然后对每个子序列进行插入排序。在对每个子序列进行插入排序时，先将当前元素保存在临时变量tmp中，然后从当前元素的前一个位置开始向前扫描，找到第一个小于等于tmp的元素，然后将tmp插入到该元素的后面。这里通过while循环实现了向前扫描的过程。重复上述过程，直到所有子序列都有序。最后，当增量gap减小到1时，整个数列就变成了一个子序列，这时再对整个数列进行一次插入排序，就可以得到最终的有序数列。希尔排序的时间复杂度约为O(N^1.3)，空间复杂度为O(1)，希尔排序是不稳定的。其代码的实现如下所示：

void shellsort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i + gap < n; i += 1)//这就相当于多组同时进行插入排序{//类似插入排序int end = i;int tmp = arr[i + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

选择排序

如果实现的是升序，从数组中遍历选出最小的放在第一个位置，然后从第二个位置遍历往后找选出第二小的放在第二个位置，再从第三个位置往后遍历选出第三小的放到第三个位置，依次类推。选择排序是不稳定的（例如待排序数组为6,7,6,5，首先选出最小的与第一个位置进行交换，这个数组将变为5,7,6,6，这个数组原本在前面的6跑到了后面，所以是不稳定的），其**时间复杂度为O(N^{2)**，如果是排升序，每次选出最小的依次往前排，所经历的次数依次是N,N-1,N-2,…,2,1,所以其时间复杂度为O(N}2)，空间复杂度为O(1)。

选择排序的示意图如下所示

选择排序的代码如下：

//交换两者之间的值
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//选择排序
void selectsort(int* arr, int n)
{for (int i = 0; i < n; i++)//遍历n趟，每趟选出从这个位置i到最后一个位置最小的{int min = i;//用min标注从i位置到最后一个位置中的最小的所在位置for (int j = i; j < n; j++){if (arr[j] < arr[min]){min = j;//更新min}}swap(&arr[i], &arr[min]);//将最小的位置的值与i位置进行交换}
}

同时选出最大和最小的，选择排序优化代码如下：

//交换两者之间的值
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//选择排序优化
void selectsort(int* arr, int n)
{for (int i = 0; i <= n / 2; i++)//遍历n/2趟，每趟选出从这个位置i到最后一个位置最小的{int max = i;//最大值所在下标int min = i;//最小值所在下标for (int j = i + 1; j < n - i; j++)//找到i位置到n-i位置最大值和最小值的下标{if (arr[j] > arr[max]){max = j;//更新max下标}if (arr[j] < arr[min]){min = j;//更新min下标}}//最大值放到最后一个位置swap(&arr[n - i - 1], &arr[max]);if (min == n - i - 1)//如果min等于n-i-1，由于上面代码进行了交换，所以最小值下标变为了max了{min = max;//更新min}//最小值放到i位置swap(&arr[i], &arr[min]);}
}

堆排序

堆排序使用的核心算法就是向下调整算法，首先用向下调整算法进行建堆。如果建的是大堆（排升序），将堆顶数据与堆中最后一个数据进行交换，再将最后这个数据不算作堆中的数据，然后使用向下调整算法将前面的数据调整成堆，直至能算作堆中的数据为0为止。注意：排升序建大堆，排降序建小堆。堆排序时间复杂度：O(NlogN)，其时间复杂度的推导可参考二叉树和堆，。其空间复杂度为O(1)，堆排序是不稳定的，堆排序的代码的实现如下：

//向下调整算法
void adjustdown(HPDataType*arr,int parents,int n)
{int child = parents * 2 + 1;while (child < n){//大堆if (child + 1 < n && arr[child + 1] > arr[child]){child++;}if (arr[child] > arr[parents]){swap(&arr[child], &arr[parents]);parents = child;child = parents * 2 + 1;}else{break;}}
}
void Heapsort(int* arr, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){//对数组进建大堆adjustdown(arr, i, n);}int k = n - 1;while (k >= 0){swap(&arr[0], &arr[k]);//堆顶与最后一个数据进行交换adjustdown(arr, 0, k);//调整之前的数据，让其成为堆k--;}
}

快速排序

快速排序就是每趟都排好一个或若干个数（这个几个数相同），将其放入到最终有序数组的位置，也就是说每一趟就将这个或者几个相同的数给排好了。快排是不稳定的，其时间复杂度为O(NlogN)。快速排序每次排好key数据，再将其分成左区间和右区间继续进行相同的操作，其过程就类似二叉树的前序遍历，层数为logN，每层都近似进行了N次遍历所以其时间复杂度为O(NlogN)，最坏的情况下其时间复杂度为O(N^2)（这通常发生在数列已经有序或者接近有序的情况下）。
如果用非递归实现的其空间复杂度为O(1)，如果用递归实现其空间复杂度为O(logN)。

递归实现排序

每次都是排好元素key。

一趟霍尔版本的快速排序的示意图(排序升序)如下：

每一趟都排好key，将key放到数组有序时key最后的位置的，进行递归key左边区间再递归key右边区间。如果是要排升序**从右边开始，右边找小找到小就停下，左边找大，左边找到大就交换这两者的值，继续右边找小，左边找大，直至两者相遇，最后将keyi位置的值与这个相遇位置进行交换，此时快排的一趟就结束了，这个值在数组中的最终位置也就排好了
霍尔版本的快排代码实现方式如下：

void quicksort(int* arr, int left, int right)
{if (left >= right)//表示区间只有一个元素或区间不存在直接返回return;int begin = left;int end = right;int keyi = left;//选择区间左边元素作为keywhile (begin < end){//一定要先右边找小，再左边找大//右边找比keyi位置值小的while (begin < end && arr[end] >= arr[keyi]){end--;}//左边找比keyi位置值小大的while (begin < end && arr[begin] <= arr[keyi]){begin++;}//两者进行交换swap(&arr[begin], &arr[end]);}//此时两者相遇(begin==end)的位置一定比keyi位置的元素小swap(&arr[begin], &arr[keyi]);//此时表示key位置的这个元素排好了，这个元素排在begin这个位置(end和begin是同一个位置)//递归begin位置的左边quicksort(arr, left, begin - 1);//递归begin位置的右边quicksort(arr, begin + 1, right);
}

挖坑法快速排序一趟示意图如下：

将坑位数据保存，减少交换次数(下面代码的实现如上动图所示)

//挖坑法快速排序
void quicksort(int* arr, int left, int right)
{if (left >= right)//区间只有一个数据或区间不存在直接返回{return;}int hole = left;//选择左边的作为坑位int key = arr[hole];//将坑位数据保存下来int begin = left;int end = right;while (begin < end){//坑位在左边所以从右边找小下标为a(小于坑位数据)，再将这个位置x的数据放入坑位，这个坑位更新为awhile (begin < end && arr[end] >= key){end--;}arr[hole] = arr[end];//将end位置的数据放入坑位hole = end;//更新坑位位置while (begin < end && arr[begin] <= key){begin++;}arr[hole] = arr[begin];hole = begin;//更新坑位位置}arr[hole] = key;//最后再将数据放入坑位quicksort(arr, left, hole - 1);//递归hole位置的左边quicksort(arr, hole + 1, right);//递归hole位置的右边
}

不将坑位保存，进行交换的方法代码如下

//挖坑法快速排序
void quicksort(int* arr, int left, int right)
{if (left >= right){return;}int hole = left;//选择左边的作为坑位int begin = left;int end = right;while (begin < end){//坑位在左边所以从右边找小下标为a(小于坑位数据)，再将这个位置x的数据与坑位数据进行交换，这个坑位更新为awhile (begin<end && arr[end]>=arr[hole]){end--;}swap(&arr[hole], &arr[end]);//交换小于坑位的数据hole = end;//更新坑位位置while (begin < end && arr[begin] <= arr[hole]){begin++;}swap(&arr[hole], &arr[begin]);//交换大于坑位的数据hole = begin;//更新坑位位置}quicksort(arr, left, begin - 1);//递归begin位置的左边quicksort(arr, begin + 1, right);//递归begin位置的右边
}

前后指针快速排序：

//前后指针法快速排序
void quicksort(int* arr, int left, int right)
{if (left >= right){return;}int key = left;//选择左边位置作为keyint prev = left;int cur = left + 1;while (cur <= right){if (arr[cur] < arr[key])//cur小于key位置的数据就prev++然后再与cur位置的数据进行交换，否则不进行交换{prev++;swap(&arr[cur], &arr[prev]);}cur++;//不论cur是大于等于或小于都需要cur++所以直接在外边进行cur++}swap(&arr[prev], &arr[key]);key = prev;quicksort(arr, left, key - 1);//递归key位置左边quicksort(arr, key + 1, right);//递归key位置右边
}

三路划分法快排，包含随机取中如果左边界大于等于右边界，则返回，递归结束。随机选择一个中轴元素，并将其与左边界元素交换位置。使用三路划分的方法，将数组分为三个部分：小于中轴元素的部分，等于中轴元素的部分，和大于中轴元素的部分。具体来说，算法使用三个指针begin、end和cur来维护这三个部分。begin指针指向小于中轴元素的部分的末尾，end指针指向大于中轴元素的部分的开头，cur指针指向当前正在处理的元素。算法首先将cur指针指向的元素与中轴元素比较，如果小于中轴元素，则将其与begin指针指向的元素交换位置，并将begin指针向右移动一位，cur指针向右移动一位。如果大于中轴元素，则将其与end指针指向的元素交换位置，并将end指针向左移动一位。如果等于中轴元素，则仅将cur指针向右移动一位。递归地对小于中轴元素的部分和大于中轴元素的部分进行排序。

//随机三数取中
int selectmid(int* arr, int left, int right)
{int mid = rand() % (right - left + 1) + left;if (arr[left] > arr[mid]){if (arr[mid] > arr[right]){return mid;}else if (arr[right] > arr[left]){return left;}else{return right;}}else//arr[left] <= arr[mid]{if (arr[mid] < arr[right]){return mid;}else if (arr[right] < arr[left]){return left;}else{return right;}}
}
//三路划分的快速排序
void quicksort(int* arr, int left, int right)
{if (left >= right){return;}//随机取中int keyi = selectmid(arr, left, right);swap(&arr[left], &arr[keyi]);keyi = left;//三路划分int begin = left;int end = right;int cur = left + 1;//三路划分升序的主要思想就是通过将小于key的数放左边大于key的数放到右边，一趟就能直接将与key相等的排好了while (cur <= end){if (arr[cur] < arr[keyi]){swap(&arr[cur], &arr[begin]);keyi = cur;//此时的cur的位置表示是keyi位置，由于上面进行了交换所以更新keyibegin++;cur++;}else if(arr[cur]>arr[keyi]){swap(&arr[cur], &arr[end]);end--;}else{cur++;}}//[left,begin-1]未排好,[begin-end]这个区间的数据已经排好,[end+1,right]未排好quicksort(arr, left, begin - 1);//递归左边区间quicksort(arr, end + 1, right);//递归右边区间
}

非递归实现快速排序

非递归的快速排序可以有效的避免栈溢出。非递归快排的实现需要借助到栈，栈当中的数据存储的是要排序的区间，栈的性质是先进后出（后进先出），存放区间的时候需要注意。每次单趟排序都排除该元素在最后有序数组中的最终位置（三路划分方法的快排是将一个或多个相同的数放到最后有序数组中的最终位置，其实是差不多的都是确定元素最终在有序数组中的最后位置）。出栈的过程很像函数栈帧的回退过程。

//交互两者之间的值
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//非递归快排
void quicksortNOR(int* arr, int left, int right)
{//创建栈stack st;stackinit(&st);if (left < right)//left小于right就将其入栈{//先入右边stackpush(&st, right);//再入左边stackpush(&st, left);}//使用栈模拟递归操作while (!stackempty(&st))//栈不为空就继续循环操作{//出栈int left = stacktop(&st);stackpop(&st);int right = stacktop(&st);stackpop(&st);//使用霍尔版本快排中的单趟排序(也可使用其他的单趟排序)，如挖坑法，前后指针或三路划分int begin = left;int end = right;int key = arr[left];//单趟排序while (begin < end){//右边找小while (begin<end && arr[end]>=key){end--;}//左边找大while (begin < end && arr[begin] <= key){begin++;}swap(&arr[begin], &arr[end]);}swap(&arr[left], &arr[begin]);if (end+1 < right){//先入右边区间stackpush(&st, right);stackpush(&st, end + 1);}if (begin-1 > left){//再入左边区间stackpush(&st, begin - 1);stackpush(&st, left);}}stacdestroy(&st);//使用完栈及时将其销毁，防止内存泄露
}

栈的代码如下：

typedef struct stack
{int* arr;//简单起见将其定义为int*int top;//指向栈顶元素int size;//栈中的元素个数
}stack;
//初始化定义的栈
void stackinit(stack* ps)
{//栈结构中的arr为置为NULLps->arr = NULL;//栈中元素个数为0ps->size = 0;//栈顶元素指向不存在的位置ps->top = -1;
}
void stackpush(stack* ps,int x)
{assert(ps);if (ps->size == ps->top + 1){//扩容操作int newsize = (ps->size == 0) ? 4 : (ps->size) * 2;int* tmp = (int*)realloc(ps->arr, sizeof(int) * newsize);if (tmp == NULL){printf("扩容失败\n");return;}ps->arr = tmp;ps->size = newsize;}ps->arr[++ps->top] = x;
}
int stacktop(stack* ps)
{assert(ps);assert(ps->top >= 0);return ps->arr[ps->top];
}
void stackpop(stack* ps)
{assert(ps);assert(ps->top >= 0);//栈中还有数据就>=0ps->top--;
}
int stacksize(stack* ps)
{assert(ps);return ps->top+1;
}
bool stackempty(stack* ps)
{assert(ps);return ps->top < 0;
}
void stacdestroy(stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->top = -1;ps->size = 0;
}

归并排序

归并排序的核心思想就是：若[left,mid]区间有序，[mid+1,right]区间也有序，将这两个有序的区间归并到一个区间[left,right]区间。归并排序需要创建一个数组用来完成拷贝。归并排序是稳定的，其时间复杂度为O(NlogN),归并排序的空间复杂度为O(N)。归并排序每次都将区间均分成左右区间，其层数为logN每层的也是遍历N次，所以其时间复杂度为O(NlogN)。
归并排序的排序动图如下:

递归实现归并排序

将两个有序的区间归并成一个有序区间，以递归的方式实现其代码如下：

void _mergesort(int* arr, int left, int right, int* tmp)
{if (left == right){return;}//将[left,right]分成[left,mid][mid+1,right]这两个区间，分别调用mergesort让着两个区间都有序int mid = left + (right - left) / 2;_mergesort(arr, left, mid, tmp);//递归左边_mergesort(arr, mid + 1, right, tmp);//递归右边区间//此时[left,mid][mid+1,right]这两个区间有序//进行归并int k = left;int begin1 = left;int begin2 = mid + 1;int end1 = mid;int end2 = right;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){tmp[k++] = arr[begin1++];}else{tmp[k++] = arr[begin2++];}}while (begin1 <= end1){tmp[k++] = arr[begin1++];}while (begin2 <= end2){tmp[k++] = arr[begin2++];}memcpy(arr + left, tmp + left, sizeof(int) * (k - left));//从left位置开始拷贝，拷贝 (k - left)个数据
}void mergesort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_mergesort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

非递归实现归并排序

归并排序的核心思想是将2个有序的数组合并到到一起，这与上面的快速排序不同，如果要实现非递归的归并排序，用栈不太合适，所以我们考虑直接用循坏的方式进行处理。首先是一个数与一个数进行合并，然后两两合并，在四四合并以此类推。归并排序是稳定的，其时间复杂度为O(NlogN)。

非递归归并排序的代码实现如下：

void mersortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}// gap每组归并数据的数据个数int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){// [begin1, end1][begin2, end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);// 第二组都越界不存在，这一组就不需要归并if (begin2 >= n)break;// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并if (end2 >= n)end2 = n - 1;int k = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (k - i));//元素个数为（k-i）个或（end2-i+1）个}gap = gap * 2;}free(tmp);//归并排序结束，释放动态开辟的空间防止内存泄漏tmp = NULL;
}

计数排序

计数排序的主要思想是将找出待排序的数组中最大和最小的元素。根据数组中元素的范围，创建一个计数数组（开辟的空间为max-min+1），用于统计每个元素出现的次数。计数数组的下标范围为 [min, max]，其中 min 和 max 分别为数组中最小和最大的元素。遍历输入数组，将每个元素在计数数组中对应的下标的计数值加 1（这个对应的下标指的是相对最小值的下标，这其实就是相对映射，也就是待排序数组中的这个值-min得到对应的下标）。再次遍历输入数组，根据每个元素在计数数组中的位置，将其放入排序后的数组中（需要注意映射回去其值应为下标+min）。计数排序是稳定的，其时间复杂度为O(N+K),其中的K表示为最大值与最小值之差+1。空间复杂度为O(K)

计数排序的代码实现如下：

void countersort(int* arr, int n)
{int max = arr[0];int min = arr[0];//找出数组中的最大值和最小值for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//开辟最大值与最小值之间的空间大小int range = max - min + 1;//使用calloc开辟range个int类型的空间并将其置0int* tmp = (int*)calloc(range,sizeof(int));for (int i = 0; i < n; i++){//arr[i]-min得到该值在tmp数组中的相对映射位置tmp[arr[i] - min]++;}int j = 0;//将数据写回arr中for (int i = 0; i < range; i++){while (tmp[i]--){arr[j++] = i + min;}}free(tmp);
}

总结：本文主要介绍了常见的排序算法，冒泡排序，插入排序，希尔排序，选择排序，堆排序，快速排序，归并排序和计数排序的代码实现以及这些排序算法的时间复杂度和空间复杂度。感谢大家观看，如有错误之处欢迎大家批评指正！！！