快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
public static void quickSort(int arr[] , int low , int high){ /** * i为指向最左边的第一个元素,j为最右边的第一个元素 , temp为基准元素 ,t为交换元素 */ int i , j , temp , t; if (low>high){ return; } i = low; j = high; temp = arr[low]; while(i<j){ while (temp<=arr[j]&&i<j){ j--; } while (temp>=arr[i]&&i<j){ i++; } //交换两个元素 if(i<j){ t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } arr[low] = arr[i]; arr[i] = temp; //递归左边 quickSort(arr , low , j-1); //递归右边 quickSort(arr , j+1 , high); } public static void main(String[] args) { List list = new ArrayList(); int arr[] = {10,3,5,7,9,2,4,6,8}; quickSort(arr,0,arr.length-1); for (int i=0 ; i<arr.length ; i++){ list.add(arr[i]); System.out.println(list); }