数据结构之八大排序算法
前言：各位铁子们好啊，博客已经好久没有更新了。今天就来看看新的文章吧。
在日常生活中，我们能够发现在许多地方会存在排序的问题。比如学校排名，成绩排名，手机销量排名等等。而常见的排序有八种，我们一起来看看都有哪八种排序算法。
1. 直接插入排序
直接插入排序的基本思想是：将待排序的关键码值按照大小插入到一个已经有序的序列中，直到将所有的关键码值插入完为止，得到一个新的有序序列。
//时间复杂度O(N^2)voidInsertSort(int* arr,int n){for(int i =0; i < n;++i){int tmp = arr[i];int end = i -1;while(end >=0){if(arr[end]> tmp){ arr[end +1]= arr[end];--end;}else{break;}} arr[end +1]= tmp;}}
若end>=0，说明应该继续比较当前end所处位置的关键码值与待排序 关键码值的大小关系。若end位置的关键码值大，就将end位置的关键 码值往后移一步，继续--end，重复上述步骤，直到end位置的关键码 值小于等于待排序的关键码值，跳出循环。此时end+1的位置就是待 排序关键码值应该插入的位置。 2. 希尔排序
希尔排序是对于直接插入排序的一种优化，又叫做缩小增量法。希尔排序的基本思想是：先选定一个整数（通常是gap=gap/3+1）,把待排序文件所有记录分成各组，所有距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序。当gap=1时，就相当于直接插入排序。
voidShellSort(int* arr,int n){int gap = n;//gap > 1都是预排序，目的是为了让数组更接近有序while(gap >1){//组数越多，循环次数多//组数越少，每组内比较的次数增多//3是一个折中的取法//+1（只有一组，相当于直接插入排序）是为了保证最后一组数据是有序的 gap = gap /3+1;for(int j =0; j < n;++j){int tmp = arr[j];int end = j - gap;while(end >=0){if(arr[end]> tmp){ arr[end + gap]= arr[end]; end -= gap;}else{break;}} arr[end + gap]= tmp;}}}
对待排序文件记录进行分组，对每一组的记录先进行排序，若 arr[end]>tmp，将当前end位置的记录往后移，更新end，继续判断 end位置的关键码值与tmp的大小关系，若arr[end]<tmp，就跳出循 环，此时end+gap就是待排序关键码值要插入的位置，再重新分 组，重复上述步骤。 希尔排序特性总结：
1.希尔排序是对直接插入排序的优化。
2.gap>1都是预排序，目的是为了让数组更加接近有序，gap=1，就相当于直接插入排序。
3. 直接选择排序
1.在元素集合arr[i]...arr[n-1]选择最小（或最大）的元素 2.若它不是这组元素中的第一个（或最后一个）元素时，就将它与这 组元素中的第一个（或最后一个）元素进行交换。 3.在剩余的元素集合中arr[i+1]...arr[n-2]，重复上述步骤，直到集合剩 余一个元素 //时间复杂度O(N^2)//直接选择排序voidSelectSort(int* arr,int n){int begin =0, end = n -1;while(begin < end){//最小值和最大值都要从begin位置开始找起，因为begin位置的元素有可能就是最大值或最小值int mini = begin, maxi = begin;//找最大，小值for(int i = begin +1; i <= end;++i){if(arr[i]> arr[maxi]){ maxi = i;}if(arr[i]< arr[mini]){ mini = i;}}if(maxi == begin){ maxi = mini;}swap(&arr[begin],&arr[mini]);swap(&arr[maxi],&arr[end]);++begin;--end;}}
从begin~end区间内mini找最小值，maxi找最大值，找到后mini位置 的元素与begin位置的元素进行交换，maxi与end元素进行交换。 4. 堆排序
堆排序是一种利用堆这种数据结构的排序算法。升序建大堆，降序建小堆。
voidAdjustDown(int* arr,int parent,int n){//左孩子int child =2* parent +1;while(child < n){//右孩子大，++childif(child +1< n && arr[child +1]> arr[child]){++child;}//孩子节点大于父节点if(arr[child]> arr[parent]){swap(&arr[child],&arr[parent]); parent = child; child =2* parent +1;}else{break;}}}//堆排序voidHeapSort(int* arr,int n){for(int i =(n -1-1)/2; i >=0;--i){AdjustDown(arr, i, n);}int end = n -1;while(end >0){swap(&arr[0],&arr[end]);AdjustDown(arr,0, end);--end;}
从最后一棵子树开始进行向下调整算法，直到根节点调整完毕，此时 为一个有效的堆。再将根节点与最后一个节点进行交换，调整堆，删 除最后一个节点。重复上述步骤，直至元素有序。 5. 归并排序
归并排序采用的是分治法，是将已有序的子序列进行合并，得到一个完全有序的序列。
void_MergeSort(int* arr,int left,int right,int* tmp){if(left >= right){return;}int mid =((right - left)>>1)+ left;//划分左右区间//左区间 [left,mid]//右区间 [mid + 1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid +1, right, tmp);//进行合并int begin1 = left, end1 = mid;int begin2 = mid +1, end2 = right;int index = begin1;while(begin1 <= end1 && begin2 <= end2){if(arr[begin1]> arr[begin2]){ tmp[index++]= arr[begin2++];}else{ tmp[index++]= arr[begin1++];}}//若某子数组有剩余元素，则将该数组剩余元素依次填充while(begin1 <= end1){ tmp[index++]= arr[begin1++];}while(begin2 <= end2){ tmp[index++]= arr[begin2++];}for(int i = left; i <= right;++i){ arr[i]= tmp[i];}}//归并排序voidMergeSort(int* arr,int n){int* tmp =(int*)malloc(sizeof(int)* n);_MergeSort(arr,0, n -1, tmp);free(tmp);}
对一个序列不断地进行划分左右区间，直到不能划分为止，再对子区 间依次进行排序，合并即可。 6. 计数排序（非比较排序）
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，操作步骤：
1.统计相同元素出现次数。
2.根据统计的结果将序列回收到原来的序列中。
//计数排序voidCountSort(int* arr,int n){//求数组内最大，最小值int max = arr[0], min = arr[0];for(int i =0; i < n;++i){if(arr[i]> max){ max = arr[i];}if(arr[i]< min){ min = arr[i];}}//开空间int gap = max - min +1;int* count =(int*)calloc(sizeof(int), gap);//统计每一个元素出现的次数for(int i =0; i < n;++i){ count[arr[i]- min]++;}//排序int index =0;for(int i =0; i < gap;++i){while(count[i]--){ arr[index++]= i + min;}}free(count);}
之所以开空间没有按照元素的个数去开空间，是因为如果元素个数非 常庞大的情况下，可能会申请失败，浪费空间。因此对原数组进行遍 历，求数组内的最大值和最小值，再开辟空间。统计原数组内每一个 元素出现的次数，根据统计的结果对序列进行排序 7. 快速排序
快速排序的基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。
7.1 hoare版本的快速排序
思路：
1.创建左右指针，确定基准值。
2.从右往左找比基准值小的，从左往右找比基准值大的，左右指针数据交换，进行下次循环。
//hoare版本int_QuickSort(int* arr,int left,int right){int key = left;//如果不++left，那么当right指向的数据都大于key(基准//值)时，会存在越界问题++left;while(left <= right){//从右往左找比基准值小的while(left <= right && arr[right]> arr[key])//arr[right] == arr[key]要不要交换{--right;}//从左往右找比基准值大的while(left <= right && arr[left]< arr[key]){++left;}if(left <= right){swap(&arr[left++],&arr[right--]);}}swap(&arr[right],&arr[key]);return right;}
right指针从右往左找比基准值小的数据，left指针从左往右找比基准值 大的数据，左右指针数据进行交换，继续重复上述步骤。跳出循环之 后，right指向的位置就是基准值的位置。 7.2 挖坑法
思路：
创建左右指针。首先从右往左找比基准值小的数据，找到后放入左边坑中，当前位置变为新的“坑”；然后从左往右找比基准值大的数据，找到后放入右边坑中，当前位置变为新的“坑”，结束循环后，将基准值放入当前“坑”中，返回当前“坑”下标。
//挖坑法int_QuickSort1(int* arr,int left,int right){int key = arr[left];int hole = left;while(left < right){//从右往左找比基准值小的while(left < right && arr[right]>= key){--right;} arr[hole]= arr[right]; hole = right;//从左往右找比基准值大的while(left < right && arr[left]<= key){++left;} arr[hole]= arr[left]; hole = left;} arr[hole]= key;return hole;}
7.3 lomuto前后指针法
思路：创建前后指针，从左往右找比基准值小的数据进行交换，使小的数据都排在基准值左边。
int_QuickSort2(int* arr,int left,int right){int key = left;int prev = left, cur = prev +1;while(cur <= right){//从左往右找比基准值小的数据if(arr[cur]< arr[key]&&++prev != cur){swap(&arr[prev],&arr[cur]);}++cur;}swap(&arr[prev],&arr[key]);return prev;}//快速排序voidQuickSort(int* arr,int left,int right){if(left >= right){return;}int key =_QuickSort(arr, left, right);//划分左右序列QuickSort(arr, left, key -1);QuickSort(arr, key +1, right);}
基准值确定之后，在对原数组进行左右区间划分，重复上述步骤。
7.4 非递归版本的快速排序
//非递归版本（栈实现）voidQuickSortNonR(int* arr,int left,int right){ Stack s;//栈初始化StackInit(&s);//栈顶插入数据StackPush(&s, right);StackPush(&s, left);//判断栈是否为空while(!StackEmpty(&s)){//取栈顶数据int begin1 =StackTop(&s);StackPop(&s);int end1 =StackTop(&s);StackPop(&s);int key = begin1;int prev = begin1;int cur = prev +1;while(cur <= end1){if(arr[cur]< arr[key]&&++prev != cur){swap(&arr[cur],&arr[prev]);}++cur;}swap(&arr[prev],&arr[key]);if(prev +1< end1){StackPush(&s,end1);StackPush(&s, prev +1);}if(begin1 < prev -1){StackPush(&s, prev -1);StackPush(&s, begin1);}}StackDestroy(&s);}先入右区间的左右端点，再入左区间的左右端点，因为栈遵从先入后出的原则。
