一、快速排序

1.基本思想：

1．先從數(shù)列中取出一個數(shù)作為基準數(shù)。
2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)。

2.演示

以一個數(shù)組作為示例，取區(qū)間第一個數(shù)為基準數(shù)。

0123456789

72	6	57	88	60	42	83	73	48	85

初始時，i = 0; j = 9; X = a[i] = 72

由于已經(jīng)將 a[0] 中的數(shù)保存到 X 中，可以理解成在數(shù)組 a[0] 上挖了個坑，可以將其它數(shù)據(jù)填充到這來。
從j開始向前找一個比X小或等于X的數(shù)。當j=8，符合條件，將a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++; 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個坑。這次從i開始向后找一個大于X的數(shù)，當i=3，符合條件，將a[3]挖出再填到上一個坑中a[8]=a[3]; j–;

0123456789

48	6	57	88	60	42	83	73	88	85

然后一直重復這個步驟即可

3.代碼

public static void quickSort(int[] arr, int begin, int end) {if (begin > end) {return ;}int i = begin;int j = end;int x = arr[i];while (i < j) {while (i < j && x < arr[j]) {j--;}if (i < j) {arr[i] = arr[j];}while (i < j && x > arr[i]) {i++;}if (i < j) {arr[j] = arr[i];}}arr[i] = x;quickSort(arr, begin, i - 1);quickSort(arr, i + 1, end);}

4.復雜度分析

s

二、4種優(yōu)化方式

1.以中樞為基準數(shù)據(jù)

public static void quickSort(int[] arr, int begin, int end) {if (begin > end) {return;}int i = begin;int j = end;int x = arr[(i + j) / 2];int temp = 0;while (i < j) {while (i < j && x < arr[j]) {j--;}while (i < j && x > arr[i]) {i++;}temp = arr[i];arr[i] = arr[j];arr[j] = temp;}quickSort(arr, begin, i - 1);quickSort(arr, i + 1, end);}

2.隨機選取基準法

public static void quickSort(int[] arr, int begin, int end) {if (begin > end) {return ;}int random = new Random().nextInt(end - begin + 1) + begin; //隨機選取基準數(shù)int i = begin;int j = end;int x = arr[random];int temp = 0;while (i < j) {while (i < j && x < arr[j]) {j--;}while (i < j && x > arr[i]) {i++;}temp = arr[i];arr[i] = arr[j];arr[j] = temp;}quickSort(arr, begin, i - 1);quickSort(arr, i + 1, end);}

3.三數(shù)取中

1.將頭部，中部，尾部數(shù)據(jù)比較大小
2.最大的數(shù)據(jù)放到最后，最小的數(shù)據(jù)放到中間，較大的數(shù)據(jù)放到頭部
3.以頭部數(shù)據(jù)為基準值

public static void newSort(int arr[], int begin, int end) {int mid = arr.length /2;if (arr[mid] > arr[end]) {swap(arr, mid, end);}if (arr[mid] > arr[begin]) {swap(arr, mid, begin);}if (arr[begin] > arr[end]) {swap(arr, begin, end);}}public static void swap(int arr[], int i, int j) {int temp = 0;temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void quickSort(int arr[], int begin, int end) {if (begin >= end) {return;}int i = begin;int j = end;if (j - i == arr.length - 1) {newSort(arr, i, j);}int x = arr[begin];while (i < j) {while (i < j && x < arr[j]) {j--;}if (i < j) {arr[i] = arr[j];}while (i < j && x > arr[i]) {i++;}if (i < j) {arr[j] = arr[i];}}arr[i] = x;quickSort(arr, begin, i - 1);quickSort(arr, i + 1, end);}

4.序列長度達到一定程度后，使用直插排序

public static void insertSort(int arr[], int i, int j) {for (int k = i + 1; k < j + 1; k++) {int insertIndex = k;int insertValue = arr[k];while (insertIndex > 0 && insertValue < arr[insertIndex - 1]) {arr[insertIndex] = arr[insertIndex - 1];insertIndex--;}arr[insertIndex] = insertValue;}}public static int quickSort(int arr[], int begin, int end) {int i = begin;int j = end;int x = arr[begin];while (i < j) {while (i < j && x < arr[j]) {j -= 1;}if (i < j) {arr[i] = arr[j];}while (i < j && arr[i] < x) {i += 1;}if (i < j) {arr[j] = arr[i];}}arr[i] = x;return i;}public static void quick_insert(int arr[], int begin, int end) {if (end - begin <= 2) {insertSort(arr, begin, end);return;}if (begin >= end) {return;}int i = quickSort(arr, begin, end);quick_insert(arr, begin, i - 1);quick_insert(arr, i + 1, end);}

總結(jié)

以上是生活随笔為你收集整理的十大经典排序算法之快速排序及其优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。