今天我们主要难点有快速排序和归并排序,会简单涉及到二叉树相关知识,相对来说比较抽象!所以如果有看不懂或者不明白的地方可以看看我之前的详解二叉树
上期学习完了前四个排序,这期我们来学习剩下的三个排序
1、冒泡排序
冒泡排序是我们相对最好理解的个排序,但是有些小优化的地方我会指出来,我们先看图解:
void BubbleSort(int* a, int n)//升序 { //时间复杂度O(N^2) while (n > 0) { int exchange = 0; for (int i = 1; ia[i]) { Swap(&a[i - 1], &a[i]);//交换 exchange = 1; } } if (exchange == 0) { break; } --n; } }
代码分析:我们每排完一趟,就可以确定最后一个位置的数,再者我们定义了一个exchange来判断在排序过程中是否发生了交换,如果没有发生交换,证明此数组已经有序,我们可以直接跳出循环,避免不必要的循环!
冒泡排序的特性总结:
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度:O(N^2) 、空间复杂度:O(1)
3. 稳定性:稳定
2、快速排序 ( 三种方法 )
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
第一种方法是我们最常见的挖坑法:
代码实现如下:
void QuickSort(int* a, int left, int right)//升序 { if (left >= right) { return; } int begin = left; int end = right; int pivot = begin; int key = a[begin]; while (begin= key) //这里如果不写begin
第二种方法左右指针法:
代码实现如下:
void QuickSort(int* a, int left, int right)//升序 { if (left >= right) { return; } int begin = left; int end = right; int keyi = begin; while (begin= a[keyi]) { --end; } //找大 while (begin
第三种方法前后指针法:
代码实现如下:
void QuickSort(int* a, int left, int right)//升序 { if (left >= right) { return; } int keyi = left; int prev = left; int cur = left + 1; while (cur <= right) { //++prev != cur为了防止自己跟自己交换造成不必要的消耗 if (a[cur]
3、归并排序
基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序我们思想还是和快排思想差不多采用分治算法,当数组被分为单独一个元素就是有序的了(见上图),在接着归并到一个数组中,即可实现排序!
代码实现如下:
void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) return; int mid = (left + right) >> 1; // 假设[left, mid] [mid + 1, right] 有序,那么我们就可以归并了 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); //归并 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1]
4、排序算法复杂度及稳定性分析
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍 在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
gitee(码云):Mercury. (zzwlwp) - Gitee.com
到此这篇关于C语言超详细讲解排序算法下篇的文章就介绍到这了,更多相关C语言 排序算法内容请搜索0133技术站以前的文章或继续浏览下面的相关文章希望大家以后多多支持0133技术站!
以上就是C语言超详细讲解排序算法下篇的详细内容,更多请关注0133技术站其它相关文章!