对于最常用的排序快速排序的思考

2019-11-06 07:43:30

字体：大中小

来源：转载

供稿：网友

快速排序的整体思想就是分治思想，选取一个基准值，从左右两边各选取一个值进行交换（左边选一个大于基准值的位置，右边选一个小于基准值的位置）。在效果上就是将一个大空间分成了左右两个小空间，然后递归再再将左右两个空间分成更小的两个空间。

它和冒泡排序最大的区别就是：冒泡每次交换的是两个相邻的数，而快排的交换距离就大得多。我们练习一下经典版的快排

int a[] = { 5, 3, 1, 8, 6, 8 };void quicksort(int left, int right){ if (left < 0 || right < 0||left>right) { return; }//选取基准值 int temp = a[left]; int i = left; int j = right; //一趟 while (i != j) { //顺序很重要，要先从右往左找 while (a[j]>=temp&&i < j)//思考：为什么要有等于号 { //因为两个相等的数交换不起什么作用，直接跳过去找合适的数 j--; } //再从左往右找 while (a[i]<=temp&& i < j) { i++; } if (i < j) { //交换两个数 int temp1 = a[i]; a[i] = a[j]; a[j] = temp1; } } //调整基准值 a[left] = a[i]; a[i] = temp; //分而治之 quicksort(left, i - 1); quicksort(i + 1, right);}

这里写图片描述