网站布局设计自适应,摄影作品网站风景,企业软文代写,网络服务器无响应改进措施或应对策略文章目录 前言1.插入排序1.1 基本思想1.2 代码实现1.3 特性总结 2.希尔排序2.1 基本思想2.2 代码实现2.3 特性总结 3. 选择排序3.1 基本思想3.2 代码实现3.3 特性总结 4. 堆排序4.1 基本思想4.2 代码实现4.3 特性总结 5. 冒泡排序5.1 基本思想5.2 代码实现5.3 特性总结 6. 快速… 文章目录 前言1.插入排序1.1 基本思想1.2 代码实现1.3 特性总结 2.希尔排序2.1 基本思想2.2 代码实现2.3 特性总结 3. 选择排序3.1 基本思想3.2 代码实现3.3 特性总结 4. 堆排序4.1 基本思想4.2 代码实现4.3 特性总结 5. 冒泡排序5.1 基本思想5.2 代码实现5.3 特性总结 6. 快速排序6.1 基本思想6.1.1 思想一6.1.2 思想二6.1.3 思想三 6.2 代码实现6.2.1 递归版本6.2.2 非递归版本 6.3 优化6.4 特性总结 7.归并排序7.1 基本思想7.2 代码实现7.2.1 递归版本7.2.2 非递归版本 7.3 特性总结 8. 计数排序8.1 基本思想8.2 代码实现8.3 特性总结 9. 总结 前言 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。不同的排序算法各有优劣本章内容讲介绍插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序、归并排序以及计数排序八大排序算法。
1.插入排序
1.1 基本思想 插入排序是一种比较简单的排序算法它的基本思想是以待排序数据的第一个数据为标准将这一个数据看为一个已排好的数据此时只看这一个数据先记为a然后将它后一个数据记为b将 b 与 a 进行比较如果 a 比 b 大就将 a 向后覆盖升序直到遇到比 b 小的或者到数据结束停止。 如图 图和代码一起看更容易理解一些。
1.2 代码实现
void InsertSort(int* a, int n)
{assert(a);int i 0;for (i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}1.3 特性总结
元素集合越接近有序直接插入排序算法的时间效率越高。时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
2.希尔排序
2.1 基本思想 先选定一个整数把待排序数据分成个组所有距离为 gap 的数据分在同一组内并对每一组内的记录进行排序。然后取上述重复分组和排序的工作。当到达 gap 1 时所有记录在统一组内排好序。 实际是先将数据分为许多组分别进行排序每一次排序都会使较小数移到前面使数据逐渐接近有序。希尔排序的过程就是先进行多次预排序分组排序的过程一直到数据间隔 gap 1 时完成所有排序。在实际中 gap 的初始值可给数据个数的一半每排完一次 gap 就除 2 直到 gap 1 时结束排序。
2.2 代码实现
void ShellSort(int* a, int n)
{int gap 3;int i 0;int j 0;//while (gap 1)//{// gap / 2; //当gap为1时就直接插入排序// for (j 0; j gap; j) //通过j变量控制i变量依次排序每个元素// {// for (i j; i n - gap; i gap) // 排一组// {// int end i;// int tmp a[end gap];// while (end 0) // 排一个// {// if (a[end] tmp)// {// a[end gap] a[end];// end - gap;// }// else// {// break;// }// }// a[end gap] tmp;// }// }//}while (gap 1){gap / 2; //当gap为1时就直接插入排序for (i 0; i n - gap; i) // 一个接一个排{int end i;int tmp a[end gap];while (end 0) // 排一个{if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}每组的数据排序采用了直接插入排序希尔排序的主要思想是需要进行多次预排序使数据逐渐有序。
2.3 特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在许多教材中给出的希尔排序的时间复杂度都不固定。稳定性不稳定
3. 选择排序
3.1 基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完
3.2 代码实现 这里进行了一点点小小的优化同时找到最大和最小值分别放到起始位置和末位置。
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//O(n*2)
void SelectSort(int* a, int n)
{int end n - 1;int begin 0;while (begin end){int mini begin, maxi end;int i 0;for (i begin; i end; i){if (a[i] a[mini])mini i;if (a[i] a[maxi])maxi i;}Swap(a[mini], a[begin]);if (begin maxi)maxi mini;Swap(a[maxi], a[end]);begin;end--;}
}值得注意的是当 begin 与 maxi 重合的情况因为我们是先交换最小值与首位置交换完后就会导致 maxi 指向的值不再是最大值而是跑到了交换后的 mini 所指向的地方因此当 begin 与 maxi 重合时在交换完后我们就需要修改 maxi 的位置使其指向正确的位置。具体如图
3.3 特性总结
直接选择排序思考非常好理解但是效率不是很好实际中很少使用。时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
4. 堆排序
4.1 基本思想 堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。具体思路在我的另一篇文章数据结构篇六二叉树中有所讲解想了解的可以点击这里进行跳转这里我就只贴上代码了。
4.2 代码实现
//向上调整
void AdjustUp(int* data, int child)
{int parent (child - 1) / 2;while (child 0){if (data[child] data[parent]) // 小堆{Swap(data[child], data[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustDown(int* data, int size, int parent)
{int child (parent * 2) 1;while (child size){if (child 1 size data[child] data[child 1]) // 大堆{child;}if (data[child] data[parent]) // 大堆{Swap(data[child], data[parent]);parent child;child (parent * 2) 1;}else{break;}}
}//堆排序
//升序 -- 大堆
//降序 -- 小堆
void HeapSort(int* a, int n)
{1.建堆 O(N*logn)int i 0;//for (i 1; i n; i)//{// AdjustUp(a, i);//}//2.建堆 O(N)for (i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}4.3 特性总结
堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
5. 冒泡排序
5.1 基本思想 根据序列中两个数据的大小来对换这两个数据在序列中的位置。这个很简单将每个数与其他数依次进行比较排序就完成了。
5.2 代码实现
void BubbleSort(int* a, int n)
{int i 0;for (i 0; i n - 1; i) //趟数{int j 0;for (j 0; j n - 1 - i; j) //每个元素比较次数{if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
}5.3 特性总结
冒泡排序是一种非常容易理解的排序。时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
6. 快速排序
6.1 基本思想 取待排序元素序列中的某元素作为基准值按照该基准值将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后左右子序列重复该过程直到所有元素都排列在相应位置上为止。
6.1.1 思想一 这里我将介绍三种快速排序的思路先看第一种。左子序列中需要所有元素均小于基准值右子序列中需要所有元素均大于基准值因此我们要在右边找小于基准值的移到左边左边找大于基准值的移到右边。 这里注意的是必须从右开始往左找这样 left 最终停止的位置才能将 key 放到正确的位置上。 这只是进行的一次排序之后就是以它为分界点对左右序列继续排序是一个不断分割 排序的过程因此我们可以考虑用递归来解决。
6.1.2 思想二 是一个挖坑的思路大体上与第一种相似略有不同。
6.1.3 思想三 用 prev 指向数据开头cur 指向 prev 的下一个再用 key 记录第一个数据当作基准值。 用 cur 从头开始找比 key 小的找到了就与 prev 的下一位置进行交换因为当前的 prev 指向的是基准值我们是从基准值的下一个位置开始排序的所以是与基准值的下一位置进行交换。本质上可以看作为 prev 前的数据包括 prev 指向的数据都是比基准值小的而完成这一效果的做法就是通过 cur 来找到比基准值小的数据然后与prev 的下一个数据进行交换再进行 prev直到cur 遍历完数据为止。 prev 之前的数据不包括 key 的位置也就是从第二个数据开始到 prev 之间都是比 key 小的而将此时的 prev 与 key 进行交换就产生了从第一个数据开始到此时 prev 之前的数据都是比 key 小的了说明这个数就排序完成了。
6.2 代码实现
int Partion1(int* a, int left, int right)
{int min GetMidIndex(a, left, right);Swap(a[left], a[min]);int key left;while (left right){//从右往左找小的while (left right a[right] a[key]){right--;}//从左往右找大的while (left right a[left] a[key]){left;}Swap(a[left], a[right]);}Swap(a[left], a[key]);return left;
}//挖坑法
int Partion2(int* a, int left, int right)
{int min GetMidIndex(a, left, right);Swap(a[left], a[min]);int pivot left;int key a[left];while (left right){//从右往左找小的放到左边的坑里while (left right a[right] key){right--;}//Swap(a[pivot], a[right]);a[pivot] a[right];pivot right;//从左往右找大的,放到右边的坑里while (left right a[left] key){left;}//Swap(a[pivot], a[left]);a[pivot] a[left];pivot left;}a[pivot] key;return pivot;
}//前后指针
int Partion3(int* a, int left, int right)
{int key left;int prev left , cur left 1;while (cur right){if (a[key] a[cur]){Swap(a[cur], a[prev]);cur;}else{cur;}}Swap(a[key], a[prev]);return prev;
}6.2.1 递归版本 三个思想每次返回的都是基准值的排序好之后的下标也就是分成了左右两个子区间用递归不断对子区间进行排序就可以了如果不太理解递归过程可以去跳转到数据结构篇六二叉树这篇文章去看一看二叉树前序遍历递归。
void QuickSort(int* a, int left, int right)
{if (left right)return;int key Partion3(a, left, right);QuickSort(a, left, key - 1);QuickSort(a, key 1, right);
}6.2.2 非递归版本 非递归的实现就需要借助栈的辅助了我们将每一次需要进行排序的区间存入栈中在每排序完一个子区间都会将这个子区间分成的更小的子区间进行压栈。每开始排序一个区间都会将该区间进行出栈同时入栈这个区间的子区间直到栈为空时说明所以区间都排序完成了。 这样不断重复就相当于模拟了递归的过程。非递归的好处在于不需要消耗太多的空间如果数据太多的话递归深度过高容易造成栈溢出非递归就很好的解决了这个问题。
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(st);StackPush(st, left); //入栈StackPush(st, right);while (!StackEmpty(st)){int end StackTop(st);//取栈顶元素StackPop(st); //出栈int begin StackTop(st);StackPop(st);int key Partion3(a, begin, end);//[begin,key - 1] key [key 1,end]if (begin key - 1){StackPush(st, begin); //入栈StackPush(st, key - 1);}if (key 1 end){StackPush(st, key 1);StackPush(st, end);}}StackDestroy(st);
}6.3 优化 大家看代码可以会看到一个GetMidIndex()这个函数这是一个对与基准值选取的优化假设第一个数据就是所有数据的最大值或者最小值那么排序会出现什么情况会出现第一次排序一直遍历完才找到相较于两边同时找会慢上很多因此才有了这个对 key 值选取的优化。
int GetMidIndex(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if(a[left] a[right]){return left;}else{return right;}}else //a[left] a[mid]{if (a[right] a[left]){return left;}else if (a[right] a[mid]){return mid;}else{return right;}}
}6.4 特性总结
快速排序整体的综合性能和使用场景都是比较好的一个排序但是对于已经比较有序的数据排序比较慢是属于一个数据越乱排序效果越好的一个算法。时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定
7.归并排序
7.1 基本思想 归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。将已经有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 本质上为两两排序四四排序……不断增加数据进行排序的过程。我们要做的就是不断分割区别再对相邻的两个区间进行排序。由于本身的数据需要进行比较因此还需要一个临时数组来保存每次排序好的数据在结束排序后再拷贝回原数组就可以了。递归过程可参考数据结构篇六二叉树这篇文章来理解。
7.2 代码实现
7.2.1 递归版本
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right)return;//进行递归分割区间int mid (left right) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);//进行排序int begin1 left, end1 mid; //左区间int begin2 mid 1, end2 right;//右区间int i left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){printf(MergeSort:);exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp NULL;
}7.2.2 非递归版本 非递归第一时间时间是结束栈或者队列来完成但是这里却不行因为我们需要将区间先不断分割到最小才开始排序而在用栈和队列模拟递归时存储的是区间的边界到栈或者队列为空时就结束了。但是在这里我们在分割到最小的区间时在排序完出队列就结束了。 也就是这一步完成之后栈或者队列就为空了就结束了无法完成排序所以不能用栈或者队列来辅助完成。 因此就要换一个思路这里是通过 gap 来控制区间不需要进行递归分割直接用循环进行控制区间通过 gap 来更改每次区间的大小。 与这个对照看更容易理解。 但是这样就会出现一个大问题gap 每次都是之前的二倍也就是每次排序的数据个数都是之前的二倍24816……那么如果是10个数据呢就会出现越界情况明明只有10个数据你却访问到了10个数据后面的空间。因此还需要对这种情况进行调整防止出现访问不该访问的地址空间的情况。 通过观看代码知道会出现越界情况的只有end1begin2end2这三个因为一个区间没有数据的话循环根本就不会进来的而有数据的话 begin1 就不会越界。end2 越界的话只需要将 end2 的值改为 n - 1 就可以了让它重新指向最后一个数据的位置就不会出现越界了begin2 越界的话将 begin2 改为 nend2 改为 n - 1这样 begin2 end2 就说明该区间不存在了就不会访问这个区间了。end1 越界的情况与 end2 越界的处理方法一致。这样就完美解决了会发生越界的问题了。
void MergeSortNonR1(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){printf(MergeSort:);exit(-1);}int gap 1, i 0; //类似层序while (gap n){for (i 0; i n; i i 2 * gap){//[i,igap-1] [igap, igap*2-1]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int j i;//end2 越界if (end2 n){end2 n - 1;}//begin2 越界 [begin2,end2]不存在,讲这个区间设置为不存在if (begin2 n){begin2 n;end2 n - 1;}//end1 越界[begin2,end2]不存在if (end1 n){end1 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}}int j 0;for (j 0; j n; j){a[j] tmp[j];}gap * 2;}free(tmp);tmp NULL;
}7.3 特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
8. 计数排序
8.1 基本思想 统计相同元素出现次数根据统计的结果将结果放回到原来的序列中。 可以理解为用新开辟出来的 count 数组来记录每个数据出现的次数count 数组的下标代表原数组的数据count 数组中存储的就是所对应下标出现的次数。 从上图看0 和 1 是没有使用到的空间有用的空间只有 2 到 9因此我们可以用最大值减去最小值加一来开辟count 数组的空间减小空间损耗。但同时下标对应的原数组数据也会发生改变比如上面的 2在存放时就需要减去最小值 2 来存放到 0 这个位置在最后放回原数组时再加上这个最小值就可以了。 不好理解的话大家可以通过画图带入数据来更加细致的理解这个过程。这也是学习数据结构内容的重要方法。
8.2 代码实现
void CountSort(int* a, int n)
{int max a[0], min a[0];int i 0;for (i 0; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* count (int*)malloc(sizeof(int) * range);if (count NULL){printf(MergeSort:);exit(-1);}memset(count, 0, sizeof(int) * range);//计数for (i 0; i n; i){count[a[i] - min];}//排序int j 0;for (i 0; i range; i){while (count[i]--){a[j] i min;}}free(count);count NULL;
}8.3 特性总结
计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围 range )稳定性稳定
9. 总结 此篇内容也是比较多跟二叉树一样也是花费了几天时间来整理叹气不过还是比二叉树好多了哎嘿。如果大家发现有什么错误的地方可以私信或者评论区指出喔官话。那么数据结构就先告一段落了接下来就要进行C和Linux的学习了希望能与大家共同进步那么本期就到此结束让我们下期再见觉得不错可以点个赞以示鼓励喔
