【数据结构】八大排序(二)
😛作者:日出等日落
📘 专栏:数据结构
在最黑暗的那段人生,是我自己把自己拉出深渊。没有那个人,我就做那个人。 ——中岛美嘉
😩快速排序:
Hoare版本(递归):
基本思想:
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,这个排序很重要
其基本思想为:
任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
(官方语言,接下来请看详细解释)
动图演示:
基本思路:
单趟排序,key一般选最左边或者最右边
★首先令key为最左边,右边先走找小,然后左边找大,然后交换位置继续,相遇则停止,相遇的值跟key对应的值交换
当左区间有序,右区间有序那整体就ok了,如果左右区间不有序,左右区间就是单趟的子问题
当区间只有一个值,就不排了,返回
代码展示:
//快速排序 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int left = begin; int right = end; int keyi = left; while (left = a[keyi]) { right--; } //左边找大 while (left a[end]) { return begin; } else { return end; } } // a[begin] > a[mid] else { //a[mid] > a[end] if (a[mid] > a[end]) { return mid; } //a[mid]完整快速排序代码:
//Hoare 版本 int PartSort1(int* a , int begin , int end) { int mid = GetmidIndex(a, begin, end); Swap(&a[begin], &a[mid]); int left = begin; int right = end; int keyi = left; while (left = a[keyi]) { right--; } //左边找大 while (left挖坑法:
基本思想:
挖坑法的思想很简单:
一开始先将left下标对应的值保存起来,然后left位置空出来的位置就是一个坑位,右边先走,找大,找到后将右边的值的数据填进去,这个right的位置就是新的坑,左边找小,再将左边找到的填进坑位,这个left对应下标的位置就是新的坑位,最后left和right一定会在坑的位置相遇
代码展示:
//挖坑法 int PartSort2(int* a, int begin, int end) { int mid = GetmidIndex(a, begin, end); Swap(&a[begin], &a[mid]); int left = begin; int right = end; int key = a[left]; int hole = left; while (left = key) { right--; } a[hole] = a[right]; hole = right; //左边找大于key的; while (left前后指针法:
动图演示:
基本思路:
1、cur下标对应的值找比key小的,找到后停下来
2、然后++prev, 交换prev位置和cur位置的值最后重复上述操作
时间复杂度:O(NlogN)
//前后指针法 int PartSort3(int* a, int begin, int end) { int prev = begin; int cur = begin + 1; int keyi = begin; while (cur
还没有评论,来说两句吧...