泊头市做网站,如何迁移wordpress网站,广州市 住房建设局网站,怎么做网站开发的方案排序#xff08;1#xff09;#xff1a;深入了解数据结构第四弹——排序#xff08;1#xff09;——插入排序和希尔排序-CSDN博客
前言#xff1a; 在前面我们已经讲过了几种排序方式#xff0c;他们的效率有快有慢#xff0c;今天我们来学习一种非常高效的排序方式…排序1深入了解数据结构第四弹——排序1——插入排序和希尔排序-CSDN博客
前言 在前面我们已经讲过了几种排序方式他们的效率有快有慢今天我们来学习一种非常高效的排序方式——快速排序 目录
一、快速排序的思想
二、快速排序的递归实现
2.1 霍尔法
2.2 挖坑法
2.3 前后指针法
三、快排的非递归实现 四、完整代码示例
五、总结 一、快速排序的思想 快速排序是一种常用的排序算法属于比较排序的一种。它的基本思想是先选取一个基准数据经过一趟排序让比它小的分为一部分比它大的分为另一部分然后再对这两部分继续这种操作直到他们有序 快速排序的具体步骤如下 选择一个基准元素通常是待排序数组的第一个元素、最后一个元素或者中间元素。将比基准元素小的元素放在基准元素的左边比基准元素大的元素放在基准元素的右边这一步称为分区操作。对基准元素左右两部分分别递归地进行快速排序。 比如这样一组数据{ 4,7,1,9,3,6,5,8,3,2,0 } 1、首先我们先选择一个基准元素我们以最左边的元素为基准元素为例 2、对剩下的元素进行排序比基准元素小的排在左边比基准元素大的排在右边 3、对小的部分和大的部分重复上面两部操作最后我们就可以得到一个有序的数组 这一步就可以清楚的看到其实快排的这种思想很像二叉树所以很容易通过类似二叉树递归的那种思想来解决
二、快速排序的递归实现
快排的实现其实是很有意思的在上面我们已经讲了快排的思想其实就是不断的重复分区操作的过程所以我们就可以设计一个递归来实现这种同时由于每一步都要进行分区所以我们可以封装一个分区排序函数PartSort函数在前重复这个过程
void QuickSort(int* a, int begin,int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}其中参数a是数组指针begin是传入数组的首元素位置end是传入元素尾元素位置过程图如下
快排函数的主体就是上面那几步接下来我们重点讲解一下快排分区排序函数PartSort函数该如何实现这一步也是非常有趣的目前我们有三种方法来实现这个函数的功能 1、霍尔排序 2、挖坑法 3、前后指针法 2.1 霍尔法 霍尔法是霍尔大佬就是快排的发明者自己刚开始用的排序方法但是由于这种分部排序方法需要注意到的点太多所以后来才又有了后面两种排序方法现在我们先来学习一下霍尔大佬的这种方法 霍尔排序其实就是严格按照我们上面讲的快排的那种思想进行的就是先选一个基准数然后对后面数进行大致的判断让比基准数小的位于基准数左侧比基准数大的位于基准数右侧 霍尔实现这个过程的方法就是先选取最左边的元素作为基准元素然后记录剩下元素左右位置然后让左边向右移动当遇到一个比基准元素大的数就停下来右边向左移动遇到一个小于基准元素的数停下来然后让左右这两个数交换 然后再讲左右两部分分开再进行类似的操作 由图可见这是一种类似二叉树的操作所以非常适合用递归来解决具体代码如下 int GetMid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[right] a[left])return left;else if (a[right] a[mid])return mid;elsereturn right;}else{if (a[right] a[left])return left;else if (a[right] a[mid])return mid;elsereturn right;}
}
//1、hero 霍尔排序
//[left,right]
int PartSort(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int keyi left;while (left right){while (left right a[left] a[keyi]){left;}while (left right a[right] a[keyi]){right--;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}但前面我们也已经提到过了霍尔排序有一些细节是一定要处理到位的就比如 1、如果取左边数为基准元素右边就要先开始移动right - -反之就左边先开始移动否则就容易可能会出现溢出的现象 2、要注意当左右移动到的那个元素等于基准元素时是要跳过的同时最后leftright时要将这个元素与基准元素交换 3、如果对于一个较为有序的函数比如{1,2,4,5,7,3,9,8},快排的效率其实是偏低的因为我们刚开始选的基准元素基本没啥作用所以我们选择的基准元素要尽可能贴近中间值所以就有了上述代码中的GetMid函数 2.2 挖坑法
鉴于霍尔法注意事项太多且霍尔法较难理解后面又有大佬总结出挖坑法这一思路相同但更形象更容易理解的方法
挖坑法的思路如下 先以左边元素为基准元素然后将这个元素挖出将这个位置理想化成一个坑然后再从右边向左边移动找到一个小于基准数的数后将它放入坑中将这个位置作为新的坑再从左边往右边去找到一个大于基准数字的数填入坑中将这个位置作为新坑直到最后将基准数字放入最后的坑中 挖坑法的思路要比霍尔法简单很多实现如下 //2、挖坑法
int PartSort2(int* a,int left,int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int key a[left];int hole left;while (left right){while (left right a[right] key){right--;}a[hole] a[right];hole right;while (leftright a[left]key){left;}a[hole] a[left];hole left;}a[hole] key;return left;
}2.3 前后指针法
前后指针法是一个更容易理解的很不错的方法体现了后人的智慧
前后指针法的思路如下 首先先将最左边元素作为基准元素然后定义一个prev表示后指针定义一个cur表示前指针curprev1然后让前指针先走当遇到一个小于基准元素的数时停下来然后让后指针走一步然后交换这两个数据直到前指针把所有数据走完 实现上述过程的代码
//3、前后指针法
int PartSort3(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}三、快排的非递归实现
这个由于篇幅问题留在下一章进行讲解其实是本人累了.......坐在这写一下午了呜呜呜呜呜........)这个明天写嘿嘿 四、完整代码示例 上面我们就已经把快排的几种分部处理的方法和思想讲的很清楚了接下来我们就通过一个完整的代码实例来感受快排的魅力所在 对数组{ 4,7,1,9,3,6,5,8,3,2,0 }进行快排
Seqlish.h
//快速排序
void QuickSort(int* a, int begin, int end);Seqlish.c
//快速排序
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
void Swap(int* e1, int* e2)
{int tmp *e1;*e1 *e2;*e2 tmp;
}
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[right] a[left])return left;else if (a[right] a[mid])return mid;elsereturn right;}else{if (a[right] a[left])return left;else if (a[right] a[mid])return mid;elsereturn right;}
}
//1、hero 霍尔排序
//[left,right]
int PartSort(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int keyi left;while (left right){while (left right a[left] a[keyi]){left;}while (left right a[right] a[keyi]){right--;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}
//2、挖坑法
int PartSort2(int* a,int left,int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int key a[left];int hole left;while (left right){while (left right a[right] key){right--;}a[hole] a[right];hole right;while (leftright a[left]key){left;}a[hole] a[left];hole left;}a[hole] key;return left;
}
//3、前后指针法
int PartSort3(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}
//递归的快速排序
void QuickSort(int* a, int begin,int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}test.c
//测试快速排序
void TestQuick()
{int a[] { 4,7,1,9,3,6,5,8,3,2,0 };PrintArray(a, sizeof(a) / sizeof(a[0]));//QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1); //递归快排QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1); //非递归快排PrintArray(a, sizeof(a) / sizeof(a[0]));
}int main()
{TestQuick();return 0;
}运行结果如下 五、总结
总之快排的思路是有点类似二叉树的所以适合用递归来解决当然用非递归同样能处理这里我们留下了一个尾巴等下次解决上面提到的这些内容如果有不理解的地方欢迎私信与我交流或者在评论区中指出
谢谢各位大佬观看创作不易还请各位大佬点赞支持一下
