快速排序的思想与归并排序思想类似，都是采用分治法的思想。将一个数组A[l...r]使用快速排序可以分解为三个主要的步骤：
- 通过随机算法获得数组A中的一个下标k，将A[k]与A[r]交换。
- 将数组分解成左右两个数组，左边数组的值均小于A[r]，右边数组的值均不小于A[r]。
- 分别对左右两个数组进行排序，这两个数组的大小均比A小。
通过上面的步骤，我们就可以得到快速排序的一个框架：
1 void QuickSortCore(int data[], int start, int end) 2 { 3 if (start < end) 4 { 5 int k = Partition(data, start, end); //分解成左右两个数组 6 QuickSortCore(data, start, k - 1); //排序左边的数组 7 QuickSortCore(data, k + 1, end); //排序右边的数组 8 } 9 }
从上面的代码中可以看出，分解A数组为左右两个数组是快速排序算法的关键，这个问题本质上为：对数组A中的某个值A[k]（k为数组的下标），将小于A[k]的数存放在数组A的前面，将不小于A[k]的数存放在数组A的后面，分界线为x。
解决该问题的一种很直观的方法就是先将A[k]与A[r]交换，然后用两个下标i、j，i表示A[0~i]中的数都小于A[r]，j从0~r-1遍历数组A。如果发现A[j]小于A[r]，则将A[i + 1]与A[j]交换，并同时增加i和j，之所以可以这样是因为A[i + 1]要么不小于A[r]，要么与A[j]相同；如果A[j]不小于M，则只递增j。最后将A[i + 1]与A[r]交换，i+1为左右数组的分界线x。
1 int Partition(int data[], int start, int end) 2 { 3 int k, i, j; 4 5 k = GetRandom(start, end); //通过随机函数获得数组下标 6 Swap(data + k, data + end); //将作为分界线的数放到最后 7 i = start - 1; 8 for (j = start; j < end; j++) 9 if (data[j] < data[end]) //需要交换 10 { 11 i++; 12 Swap(data + i, data + j); 13 } 14 i++; 15 Swap(data + i, data + end); 16 return i; 17 }
解决问题的另一个方法是先将A[k]与A[l]交换，并用一个临时变量p保存A[k]，也使用两个下标i和j，分别初始化为l和r。开始用j从数组右边遍历，知道发现A[j] < p为止，将A[j]赋值给A[i]，并让i加1，然后用i从数组的左边遍历，知道发现A[i] > p为止，将A[i]赋值给A[j]，并让j减1，然后重新开始前面的遍历，知道i == j为止。最后将p赋值给A[i]，此时i为左右数组的分界线x。
1 int Partition(int data[], int start, int end) 2 { 3 int k, i, j, temp; 4 5 k = GetRandom(start, end); 6 Swap(data + k, data + start); //将基准数放到最前面 7 temp = data[start]; //保存基准数副本 8 i = start; 9 j = end; 10 while (i < j) 11 { 12 //从右边开始遍历，知道遇到小于temp的 13 while (i < j && data[j] >= temp) 14 j--; 15 if (i < j) 16 data[i++] = data[j]; 17 //从左边开始遍历，知道遇到大于temp的 18 while (i < j && data[i] <= temp) 19 i++; 20 if (i < j) 21 data[j--] = data[i]; 22 } 23 data[i] = temp; 24 return i; 25 }
前面两个方法中，第二个方法比第一个方法要好些，第二个方法用赋值替代了第一个方法中的交换。
代码中的GetRandom函数是用来随机获得start到end之间的一个值，它可以用rand库函数实现。