数据结构-八大排序之快速排序

快速排序（quick sort）

一、思路

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。

二、例子

步骤：

1.定义待排序数组当中的第一个值作为基准数（base）

2.定义 j 游标，从后往前移动找到第一个比基准数小的值停下

3. 定义i 游标，从前往后移动找到第一个比基准数大的值停下。

4. i和j数值交换

5. 重复2-4直到 i和j 相遇

6. 基准数和相遇位置的数据进行交换，交换完成之后基准数到达正确位置。

7. 以基准数为起始点，分成左右两部分，重复上述所有，直到数据都被拆分开停止。

---

三、时间复杂度

第一轮： 1个数组   2^0   1个数据到达正确位置

第二轮： 2个数组  2^1    2个数据到达正确位置

第三轮：4 个数组  2^2   4个数据到达正确位置

...

第k轮：  2^(k-1)个数组    2^(k-1)个数据到达正确的位置

x=1+2+4+...+2^(k-1)

x=2^k-1

k=log2x

O(nlogn)

---

四、代码

代码

package com.lojarro.排序;import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr,int left,int right) {if(left>=right) {return;}	//定义变量保存基准数int base=arr[left];//定义i游标j游标int i=left;int j=right;while(i!=j) {//j游标从后往前移动，找比基准数小的while(arr[j]>=base&& i<j) {j--;}while(arr[i]<=base&&i<j) {i++;}//i和j进行交换int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}//i和j相遇 基准数和相遇位置进行交换arr[left]=arr[i];arr[i]=base;//排序左边sort(arr,left,i-1);//排序右边sort(arr,i+1,right);}
}

内存图