福州制作公司网站,青岛模板网站,潍坊企业模板建站,国际型网站建设Hello#xff0c;大家好#xff0c;今天分享的八大排序里的快速排序#xff0c;所谓快速排序是一个叫霍尔的人发明#xff0c;有很多人可能会觉得为什么不叫霍尔排序#xff0c;其中原因就是因为它快#xff0c;快速则体现了它的特点#xff0c;今天我们就来讲一下快速排… Hello大家好今天分享的八大排序里的快速排序所谓快速排序是一个叫霍尔的人发明有很多人可能会觉得为什么不叫霍尔排序其中原因就是因为它快快速则体现了它的特点今天我们就来讲一下快速排序现在开始我们的学习吧。 快速排序 1.基本思想 通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。 实现逻辑
快速排序使用分治法Divide and conquer策略来把一个序列list分为两个子序列sub-lists。
① 从数列中挑出一个元素称为 “基准”pivot ② 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作。 ③ 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归到最底部时数列的大小是零或一也就是已经排序好了。这个算法一定会结束因为在每次的迭代iteration中它至少会把一个元素摆到它最后的位置去。 我们来看一下它的图是怎么实现的 首先我们给定它一个数组并且定义左边为left右边为right然后我们的有个中间值中间值这里我们就叫它为k定义这个k是从left开始当然我们也可以从right开始等一下会来讲原因现在我们只要看懂它的图就行 因为是从左边开始所以要从右边先走原因是我们这样才能确定left和right相遇的时候的值一定比k的值小这里再详细展开讲解一下我们的left和right相遇有两种可能一种是left和right相遇这个时候相遇是怎样的呢因为right先走遇到比k小的时候停下来然后left又开始走除非遇到比l大的值才会停下否则就继续但是我们还有一个结束条件那就是left要小于right所以如果left没有找到比k大的值他们就会相遇那这样的话因为我们right找到小的值了所以最后k肯定比right所指向的值要大还有一个就是我们right遇到left那同样的道理说明我们的right没有找到比k大的值所以相遇之后也是一样的道理结论就是相遇的值一定比k指向的值小。那我们再继续来看图 这个时候我们的right找到比k小的值然后才开始动left那我们现在开始动left left也找到了那现在就是交换它们的这里我们用一个swap函数就可以了因为后面还需要用到swap这个函数的交换之后变成这样的 可以看到先在我们已经开始交换我们找值需要一个两个while外面还需要一个大while控制
那我们现在可以继续开始动right了 这下又找到了 开始动left 那现在我们需要交换他们 现在我们也交换好了现在right在走一步就会爆炸小编是小黑子实锤了这个时候循环就应该结束 我们需要做的就是在循环外面再进行k和left的交换
void swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
int PartSort(int* a,int left, int right)
{int k left;while (left right){while ( a[right] a[k]){right--;}while ( a[left] a[k]){left;}swap(a[left], a[right]);}swap(a[left], a[k]);return left;
}这里其实会有问题有两个问题一个是会存在越界一个就是会出现死循环先讲一下死循环的例子比如我们再第一次找left和right的值这两个值的大小是相等的那他们进行交换之后left和right的值就不会变了因为循环他们进不去了所以要加一个等于的条件就行了还有就是越界我们之前讲过越界就像查酒驾一样是有随机性的为什么会越界是因为right可能一直找不到小的值然后就会比left还小所以我们只需要加上一个条件就行了 看看代码
void swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
int PartSort(int* a,int left, int right)
{int k left;while (left right){while (left right a[right] a[k]){right--;}while (left right a[left] a[k]){left;}swap(a[left], a[right]);}swap(a[left], a[k]);return left;
}现在就是这只是我们走了一遍并不能实现将他们变成有序数列所以这里我们就可以用递归进行遍历怎么进行遍历为什么能进行遍历呢我们来分析 会这样分成左边和右边然后再左边和右边再进行我们上面的操作那是不是和二叉树很 相似的所以我们递归实现一下这里不过多的讲解等我更新二叉树的文章后大家可能看起来就明白了
void QuickSort(int* a, int begin,int end)
{ if (begin end)return;int ret PartSort(a, begin, end);QuickSort(a, begin, ret - 1);QuickSort(a, ret 1, end);
}
完整代码加测试代码
void swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
int PartSort(int* a,int left, int right)
{int k left;while (left right){while (left right a[right] a[k]){right--;}while (left right a[left] a[k]){left;}swap(a[left], a[right]);}swap(a[left], a[k]);return left;
}void QuickSort(int* a, int begin,int end)
{ if (begin end)return;int ret PartSort(a, begin, end);QuickSort(a, begin, ret - 1);QuickSort(a, ret 1, end);
}#includestdio.h
int main()
{int arr[] { 6,1,2,7,9,3,4,10,8 };QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}return 0;
} 反正最后排序成功了这个挡住了一部分结果我换个大的 好好好今天的学习就到这吧拜拜。。。。
