【数据结构】八大排序(超详解+附动图+源码) |
您所在的位置：网站首页 › intj八大功能排序 › 【数据结构】八大排序(超详解+附动图+源码) |
【数据结构】八大排序(超详解+附动图+源码)
|
目录 前言 常见排序算法的实现 1.插入排序 2.希尔排序 3.选择排序 4.堆排序 5.冒泡排序 6.快速排序 6.1 hoare版本 6.2挖坑法 6.3前后指针法 6.4快速排序优化 6.5快速排序非递归实现 7.归并排序 7.1递归实现 7.2非递归实现 8.计数排序(了解) 排序算法复杂度及稳定性分析 前言所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 生活中各种地方都需要用到排序，所以学好排序算法是非常重要的。 排序分为 内部排序 和 外部排序。 内部排序：数据元素全部放在内存中的排序。外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。 这部分主要是内部排序。排序讲解都以升序为例。 常见的排序算法：
思想： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 实际中我们玩扑克牌时，就用了插入排序的思想：
演示过程动图： 单趟：若数组(arr)除最后一个元素外其余全部有序，设最后一个元素的下标为i，将arr[i]与前面的元素比较，前面的元素比他大则前面的元素向右移动，比他小则在该元素的后面插入。
复合：因为不知道数组中得到前几个元素是已经有序的，所以直接从第二个元素开始执行插入排序，单个过程与上述相同，将每个元素都进行一次插入排序。
代码如下： // 插入排序 void InsertSort(int* a, int n) { assert(a); int i = 0; for (i = 0; i < n - 1; i++)//因为x元素位置是i的下一个位置，为防止x越界，需要使 i < n-1 { int end = i;//已经有序的最后一个元素(一个元素不需要排序，所以默认从0开始) int x = a[end + 1];//需要排序的元素 //单趟 while (end >= 0) { //若前一个数字大于x，则需将他向右移动 if (a[end] > x) { a[end + 1] = a[end]; //继续判断前面的元素 --end; } //前面元素小于x else { break; } } //将x插入正确位置(两种情况) //1.前面的数字小于x //2.前面的数字都大于x，x放在下标为0处 a[end + 1] = x; } }直接插入排序的特性总结： 元素集合越接近有序，直接插入排序算法的时间效率越高时间复杂度：O(N^2)空间复杂度：O(1)，它是一种稳定的排序算法稳定性：稳定 2.希尔排序希尔排序法又称缩小增量法。 基本思想： 先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。 然后将gap逐渐减小重复上述分组和排序的工作。 当到达gap=1时，所有元素在统一组内排好序。 静态图演示：
动图演示： 这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。
代码如下： // 希尔排序 void ShellSort(int* a, int n) { assert(a); int gap = n; while (gap > 1) { //gap /= 2; gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } } }希尔排序的特性总结： 希尔排序是对直接插入排序的优化。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。时间复杂度O(N^1.5)空间复杂度O(1)稳定性：不稳定。 3.选择排序基本思想： 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置， 然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置， 重复这样的步骤直到全部待排序的数据元素排完 。 动图演示：
代码入下： 这里我们可以进行一个优化，最小值和最大值同时选，然后将最小值与起始位置交换，将最大值与末尾位置交换。 // 选择排序 void SelectSort(int* a, int n) { assert(a); int begin = 0;//保存数组的起始位置 int end = n - 1;//保存换数组的末尾位置 while (begin < end) { int maxi = begin;//保存最大元素下标 int mini = begin;//保存最小元素下标 //遍历数组寻找最小和最大元素 for (int i = begin; i a[maxi]) { maxi = i; } } //将最小元素交换到起始位置 Swap(a+begin, a+mini); //判断最大值的位置是否在起始位置 if (maxi == begin) { maxi = mini; } //将最大元素交换到末尾位置 Swap(a+end, a+maxi); //移动数组起始和末尾位置 begin++; end--; } }注意： 在进行最小值和最大值同时交换时也会出现一个问题， 如果最大值在起始位置的时候，交换了最小值之后，最大值就被交换到了min的位置， 如果继续交换max，就会将最小值交换到末尾位置。
所以，在每次交换了最小值之后应该判断一下最大值是否在起始位置，如果在需要将max赋值为min。
直接选择排序的特性总结： 直接选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用 时间复杂度：O(N^2) 空间复杂度：O(1) 稳定性：不稳定 4.堆排序堆排序即利用堆的思想来进行排序，总共分为两个步骤： 1. 建堆 升序：建大堆降序：建小堆2. 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。 这里以升序为例： 首先应该建一个大堆，不能直接使用堆来实现。可以将需要排序的数组看作是一个堆，但需要将数组结构变成堆。我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶，这样就可以将数组调整成一个堆，且如果建立的是大堆，堆顶元素为最大值。然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。动图演示： 注意：实际中并没有删除堆中元素，图中为了方便表示，将交换后的位置画成了空。
代码如下： // 堆排序 void AdjustDown(int* a, int n, int root)//向下调整 { assert(a); int parent = root; int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { assert(a); //建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //交换 for (int i = n - 1; i > 0; i--) { Swap(&a[i], &a[0]); AdjustDown(a, i, 0); } }直接选择排序的特性总结： 堆排序使用堆来选数，效率就高了很多。时间复杂度：O(N*logN)空间复杂度：O(1)稳定性：不稳定 5.冒泡排序冒泡排序应该是我们最熟悉的排序了，在C语言阶段我们就学习了冒泡排序。 他的思想也非常简单： 两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟 一共进行n-1趟这样的交换将可以把所有的元素排好。 (n-1趟是因为只剩两个元素时只需要一趟就可以完成) 动图演示：
代码如下： // 冒泡排序 void BubbleSort(int* a, int n) { assert(a); int i = 0; int flag = 0; //n-1趟排序 for (i = 0; i < n-1; i++) { int j = 0; //一趟冒泡排序 for (j = 0; j < n - i - 1; j++) { if (a[j] > a[j+1]) { Swap(&a[j], &a[j+1]); flag = 1; } } //若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序 if (flag == 0) { break; } } }冒泡排序的特性总结： 冒泡排序是一种非常容易理解的排序时间复杂度：O(N^2)空间复杂度：O(1)稳定性：稳定 6.快速排序这里是排序算法的重点了，非常重要！ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法， 其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 6.1 hoare版本具体思路是： 选定一个基准值，最好选定最左边或者最右边，选中间会给自己找麻烦。确定两个指针left 和right 分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换left和right指针对应位置的值。重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。这样基准值左边的所有数都比他小，而他右边的数都比他大，从而他所在的位置就是排序后的正确位置。 之后再递归排以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。 动图演示： 这里选定基准值为最右边的元素。
单趟图解：
继续按照上述步骤进行。。。
代码如下： // 快速排序hoare版本 int PartSort1(int* a, int left, int right) { int key = right;//选定基准值 while (left < right) { //选右边为基准值，左指针先走 while (left < right && a[left] = a[key]) { right--; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[key]); return left; } void QuickSort(int* a, int left, int right) { assert(a); if (left >= right) { return; } int keyi = PartSort1(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } 6.2挖坑法挖坑法与上面的方法类似。 具体思路是： 先将选定的基准值(最左边)直接取出，然后留下一个坑， 当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位，然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位，重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。之后也是以基准值为界限，递归排序基准值左右区间。 动图演示：
这里不再单趟演示该过程。。。 代码如下： // 快速排序挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left];//取出基准值 int hole = left;//保存坑的位置 while (left < right) { while (left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; while (left < right && a[left] = right) { return; } int keyi = PartSort2(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } 6.3前后指针法前后指针法是一个新思路，不太好理解，但是代码比较简单。 具体思路是： 选定基准值，定义prev和cur指针(cur = prev + 1)cur先走，遇到小于基准值的数停下，然后将prev向后移动一个位置将prev对应值与cur对应值交换重复上面的步骤，直到cur走出数组范围最后将基准值与prev对应位置交换递归排序以基准值为界限的左右区间动图演示：
单趟演示： 代码如下： // 快速排序前后指针法 int PartSort3(int* a, int left, int right) { //1.将基准值定在left int keyi = left; int prev = left; int cur = left + 1; while (cur a[right]) { return right; } else { return mid; } } else { if (a[mid] > a[left]) { return left; } else if (a[mid] < a[right]) { return right; } else { return mid; } } }2.类似于二叉树，每个子树都会进行一次递归调用，越到下面递归调用会越多。为了减少递归调用，当到递归到下层时，我们可以使用其他的排序来替代。这里我们使用插入排序。
以前后指针法为例，完整代码为： // 快速排序前后指针法 int PartSort3(int* a, int left, int right) { int mid = MidIndex(a, left, right); //将基准位置调整至最左边 Swap(&a[mid], &a[left]); //1.将基准值定在left int keyi = left; int prev = left; int cur = left + 1; while (cur mid+1) { StackPush(&st, right); StackPush(&st, mid + 1); } if (left < mid - 1) { StackPush(&st, mid - 1); StackPush(&st, left); } } StackDestroy(&st); }快速排序的特性总结： 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 时间复杂度：O(N*logN) 空间复杂度：O(logN) 稳定性：不稳定 7.归并排序 7.1递归实现基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
按照其算法思想： 首先应在数组中找出有序的序列，但数组是否有序编译器可不知道。 所以可以将数组划分，一分二，二分四......直到每个序列中只有一个数字。 一个数字总可以认为他是有序的吧。 最后将同时划分的序列合并。 动图演示：
代码如下： 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;//有序序列1 int begin2 = mid + 1, end2 = right;//有序序列2 int i = left; while (begin1 = n) { end2 = n - 1; } //归并 while (begin1 |
【本文地址】
今日新闻 |
推荐新闻 |