赞
踩
快速排序是对起泡排序(冒泡排序)的改进,采用分治思想。在各种排序方法中,快速排序比较次数较少,速度较快。
给出一组待排序的数据记录。我们需要选择一个基准值作为分区标准,通常我们取第一个记录或者最后一个记录作为基准值。然后再将所有小于该基准值的记录移到左边,将所有大于该基准值得记录移到右边,中间放基准值记录,称为一趟排序。接着,对左右两个子序列分别重复上述过程。继续下去,直到所有的记录都排好序。
例题:
待排序的数组:{5,7,2,9,1,4,6,8,10,3}
期望排好序后的数组:{1,2,3,4,5,6,7,8,9,10}
例题解析:
第一步:选择数组的第一个数据作为基准值,即 5
第二步:首先从左边开始,也就是从第二个数据开始与基准值比较。若小于基准值,则继续比较下一条数据;若大于基准值,则停止比较,并记录下大于基准值的数据的索引(下标)
第三步:从最右边的数据与比较起,若大于基准值,则继续比较下一条数据;若小于基准值,则停止比较,并记录下小于基准值的数据的索引(下标)
第四步:将左边大于基准值的数据与右边小于基准值的数据交换。
第五步:重复第二、三、四步,直到将数组中所有数据比较完。这时需要将第一个数据也就是基准值交换到左右分好的序列中间来。这时数组分成两边,左边的数据都小于基准,右边的数据都大于基准值。
第六步:将左右两边的数据分别重复以上五个步骤,直到所有数据排好序。注意,接下来的每一趟排序不是以5作为基准值了,而是以左右两边的数据的第一个数据作为基准值。
例题数组的每一趟排序的结果:
【】内是下一趟要比较的序列
第一趟后:{【1,3,2,4】,5,【9,6,8,10,7】}
第二趟后:{1,【3,2,4】,5,9,6,8,10,7}
第三趟后:{1,2,3,4,5,【9,6,8,10,7】 }
第四趟后:{1,2,3,4,5,【7,6,8】,9,【10】 }
第五趟后:{1,2,3,4,5,【6 】,7,【 8 】,9,10 }java实现的代码:
- public class QuickSort {
- public static void main(String[] args) {
- //要进行排序的数组
- int[] a = {5,7,2,9,1,4,6,8,10,3};
-
- //将数组a从小到大排序
- quickSort(a, 0, a.length-1);
-
- //打印数组
- printArray(a);
- }
- /**
- * 快速排序
- * 将数组a的某一段元素进行划分,小的在左边,大的在右边
- * @param a
- * @param left
- * @param right
- */
- private static void quickSort(int[] a, int left, int right) {
- //如果只有一个元素,就不用再排下去了
- if(left < right){
-
- int pivot = a[left]; //用序列最左边的记录作为基准值
- int i = left, j = right;
-
- while(i < j){
- //从左边开始遍历,如果比基准值小,就继续向右走
- while(i < j && a[i] <= pivot) i++;
- //从右边开始遍历,如果比基准值大,就继续向左走
- while(i < j && a[j] > pivot) j--;
-
- //上面的while循环结束时,就说明当前的a[i]的值比基准值大,
- //当前的a[j]的值比基准值小,a[i]应与a[j]互换
- if(i < j){
- swap(a, i, j);
- }
- }
- //分组结束后,要将基准值交换到两组之间
- swap(a, left, i-1);
- //继续递归排序左边的序列
- quickSort(a, left, i-2);
- //继续递归排序右边的序列
- quickSort(a, i, right);
- }
-
- }
-
- /**
- * 交换数组a中索引为 i 和 j 之间的数值
- * @param a
- * @param i
- * @param j
- */
- private static void swap(int[] a, int i, int j) {
- int temp = a[i];
- a[i] = a[j];
- a[j] = temp;
- }
-
- //打印数组
- private static void printArray(int[] a) {
- for(int i = 0;i < a.length;i++){
- System.out.print(a[i] + " ");
- }
- }
- }

python实现的代码:
- def quickSort(a, l, r):
- if l < r:
- pivot = a[l]
- i = l
- j = r
- while i < j:
- while i < j and a[i] <= pivot:
- i += 1
- while i < j and a[j] > pivot:
- j -= 1
-
- if i < j:
- swap(a, i, j)
-
- swap(a, l, i-1)
- quickSort(a, l, i-2)
- quickSort(a, i, r)
-
- def swap(a,i,j):
- temp = a[i]
- a[i] = a[j]
- a[j] = temp
-
-
- a = [5,7,2,9,1,4,6,8,10,3]
- quickSort(a,0,len(a)-1)
- print(a)

C++实现的代码与java的代码基本一样,只需要修改极少的部分:
- #include <iostream>
- using namespace std;
-
- /**
- * 交换数组a中索引为 i 和 j 之间的数值
- * @param a
- * @param i
- * @param j
- */
- void swap(int a[], int i, int j)
- {
- if(i != j)
- {
- int temp = a[i];
- a[i] = a[j];
- a[j] = temp;
- }
- }
- //打印数组
- void printArray(int a[], int len)
- {
- for(int i = 0;i < len;i++)
- {
- cout<<a[i]<<" ";
- }
- }
-
- void quickSort(int a[], int left, int right) {
- //如果只有一个元素,就不用再排下去了
- if(left < right){
-
- int pivot = a[left]; //用序列最左边的记录作为基准值
- int i = left, j = right;
-
- while(i < j){
- //从左边开始遍历,如果比基准值小,就继续向右走
- while(i < j && a[i] <= pivot) i++;
- //从右边开始遍历,如果比基准值大,就继续向左走
- while(i < j && a[j] > pivot) j--;
-
- //上面的while循环结束时,就说明当前的a[i]的值比基准值大,
- //当前的a[j]的值比基准值小,a[i]应与a[j]互换
- if(i < j){
- swap(a, i, j);
- }
- }
- //分组结束后,要将基准值交换到两组之间
- swap(a, left, i-1);
-
- //继续递归排序左边的序列
- quickSort(a, left, i-2);
- //继续递归排序右边的序列
- quickSort(a, i, right);
- }
-
- }
-
-
-
-
- int main(int argc, char* argv[])
- {
- int a[] = {5,7,2,9,1,4,6,8,10,3};
- int len = sizeof(a)/sizeof(int);
- quickSort(a, 0 , len-1);
- printArray(a, len);
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。