1.快速排序简介:
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
2.快速排序原理:
a.先选一个基准值(key),一般选取序列第一个数作为基准值。假设最右边的索引为J,最左边的索引为i.
b.先从右往左比较,(进行j--)直到找到第一个比key小的数,然后把他与key进行交换。
c.在从左往右比较,(进行i++)直到找到第一个比key大的数,然后把他与key进行交换。
d.直到i==j,结束第一次循环。此时,key左边的数都比key小,key右边的数都比key大,原序列被分为两个子序列。
e.递归。将这两个子序列在重复上面a,b,c,d四个步骤。
3.java代码实现
package harbin; import java.util.Scanner; public class QSort{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); System.out.println("请输入要进行排序的数列的长度: "); int n = sc.nextInt(); int [] a = new int[n]; System.out.println("请输入要进行排序的数列: "); for(int i=0;i<n;i++){ a[i] = sc.nextInt(); } int x = 0; int y = a.length-1; QSort.QuickSort(a,x,y); for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } public static void QuickSort(int[] a,int start,int end){ int left = start; int right = end; int key = a[start]; while(left<right){ while(left<right&&a[right]>=key){//从后向前寻找第一个比key小的值 right--; } if(a[right]<=key){ int temp = a[left]; a[left] = a[right]; a[right] = temp; } while(left<right&&a[left]<=key){//从前向后寻找第一个比key大的值 left++; } if(a[left]>=key){ int temp = a[left]; a[left] = a[right]; a[right] = temp; } } if(left>start){ QuickSort(a,start,left-1); } if(right<end){ QuickSort(a,right+1,end); } } }