快速排序的核心是要有一个基准数据temp,一般取数组的第一个位置元素。然后需要有两个指针left和right,分别指向数组的第一个和最后一个元素。
首先从right开始,比较right位置元素和基准数据。如果大于等于,则将right指针左移,比较下一位元素;如果小于,就将right指针处数据赋给left指针处(此时left指针处数据已保存进temp中),left指针+1,之后开始比较left指针处数据。
拿left位置元素和基准数据进行比较。如果小于等于,则将left指针右移,比较下一位元素;而如果大于就将left指针处数据赋给right指针处,right指针-1,之后开始比较right指针处数据…重复这个过程。
直到left和right指针相等时,说明这一次比较过程完成。此时将先前存放进temp中的基准数据赋值给当前left和right指针共同指向的位置处,即可完成这一次排序操作。
之后递归排序基础数据的左半部分和右半部分,递归的过程和上面讲述的过程是一样的,只不过数组范围不再是原来的全部数组了,而是现在的左半部分或右半部分。当全部的递归过程结束后,最终结果即为排好序的结果。
快速排序执行示意图:
/** 快速排序** 参数说明:*a -- 待排序的数组*l -- 数组的左边界(例如,从起始位置开始排序,则l=0)*r -- 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)*/void quick_sort(int a[], int l, int r){if (l < r){int i,j,x;i = l;j = r;x = a[i];while (i < j){while(i < j && a[j] > x)j--; // 从右向左找第一个小于x的数if(i < j)a[i++] = a[j];while(i < j && a[i] < x)i++; // 从左向右找第一个大于x的数if(i < j)a[j--] = a[i];}a[i] = x;quick_sort(a, l, i-1); /* 递归调用,排序锚点左边部分 */quick_sort(a, i+1, r); /* 递归调用,排序锚点右边部分*/}}