原理:选择一个关键值作为基准值。比基准值小的都在左边序列(无序的),比基准值大的都在右边(无序的)。一般选择序列的第一个元素。
一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。接着分别比较左右两边的序列,重复上述的循环。
下面是流程图:
image.png image.png明白了原理,以下举例说明,代码实现,数组重改:
int quickArr[] = new int[] {7,2,6,8,1,4,9,3,10,5};
quickSort(quickArr, 0, quickArr.length - 1);
/**
* 快速排序
*/
private void quickSort(int arr[], int low, int high) {
if (low > high) {
return;
}
//7为基数
int base = arr[low];
int i = low;
int j = high;
while (i != j) {
//从右边找比base小的值为止
while (i < j && arr[j] > base) {
j--;
}
arr[i] = arr[j];
//从左边找比base大的值位置
while (i < j && arr[i] < base) {
i++;
}
arr[j] = arr[i];
//一次从右向左和一次从左向右比较的结果
for (int m=0;m<arr.length;m++) {
Log.d(TAG, "quickSort==>i="+i+", j="+j+", arrStr="+arr[m]);
}
}
arr[i] = base;
for (int n=0;n<arr.length;n++) {
Log.d(TAG, "quickSort==>一轮比较结果==>arrStr="+arr[n]);
}
/**
* 5,2,6,3,1,4, [7], 9,10,8
* 比完一轮之后,基数7左边的全部小于7,右边的大于等于7
* 再将左边两边的数组分别递归排序即可
*/
quickSort(arr, low, i-1);
quickSort(arr, i+1, high);
}
输出为:
1
2
2
3
4
4
7
7
8
9
10
网友评论