快速排序算法 快速排序算法的平均时间复杂度为

快速排序算法总结：

平均时间复杂度O(NlogN) 最差的情况每次都比较情况下O(N*N)

算法的思想：

条件：

1.基准值作为比较值，一般都取得是第一个元素

2.两个哨兵值，一个从左边开始扫描的哨兵i和一个从右边开始扫描的哨兵j

3.当两个哨兵相遇的时候交换哨兵的值和基准值，完成一次循环的比较

4.相遇的值也就是基准值把该数组分成两个数组，一个全部小于基准值的数组，一个全部大于基准值的数组,也就是二分查找的思想。

5.两个数组重现开始排序，循环的递归和二分查找操作。

Java代码的实现:

public class QuickSortTest {

public void main (){

//定义一个数组

int[] arr = {23,984,263,9,18,47,56,2,34,23,11,14,78};

//定义一个排序的方法

quickSort(arr,0,arr.length-1);

for (int i = 0; i < arr.length; i++) {

System.out.println(arr[i]);

}

}

/**

* 快速排序算法

* @param arr

* @param low

* @param high

*/

private void quickSort(int[] arr, int low, int high) {

//校验数组只有一个元素时不比较

if (low >= high) {

return;

}

//1.定义基准值,哨兵值i哨兵j,交换值t

int temp = arr[low]; // 不能写死，循环递归用参数值

int i = low;

int j = high;

int t;

//2.开始从右边和左边开始扫描,右边小于的值和左边大于的数值进行交换处理,

while (i<j) { //前提条件是i<j的情况下比较

//从右边开始递减处理 大于基准值是正常的

while (temp <= arr[j] && i<j) {

j--;

}

//从左边开始递增 小于基准值是正常的

while (temp >= arr[i] && i < j) {

i++;

}

//两边都是不正常的情况下开始交换数值

if (i < j) { //保证大前提是i<j

t = arr[j];

arr[j] = arr[i];

arr[i] = t;

}

}

//3.前提条件i=j两个哨兵相遇之后,交换基准值和相遇值

arr[low] = arr[i];

arr[i] = temp;

//4.开始二分查找的循环递归,直到两边的数组排序完成

quickSort(arr,low,j-1);

quickSort(arr,j+1,high);

}

}