【Java】实现快排算法

客官°小女子只卖身不卖艺 2021-09-21 10:06 333阅读 0赞

一：快排算法简述  
快速排序是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序，下面我们简单进行阐述。

二：快排思路  
我们从一个数组来逐步逐步说明快速排序的方法和思路。

> 假设我们对数组\{7, 1, 3, 5, 13, 9, 3, 6, 11\}进行快速排序。  
> 1:首先在这个序列中找一个数作为基准数，为了方便可以取第一个数。  
> 2:遍历数组，将小于基准数的放置于基准数左边，大于基准数的放置于基准数右边。  
> 3:此时得到类似于这种排序的数组\{3, 1, 3, 5, 6, 7, 9, 13, 11\}。  
> 4: 在初始状态下7是第一个位置，现在需要把7挪到中间的某个位置k，也即k位置是两边数的分界点。  
> 5:那如何做到把小于和大于基准数7的值分别放置于两边呢，我们采用双指针法，从数组的两端分别进行比对。  
> 6:先从最右位置往左开始找直到找到一个小于基准数的值，记录下该值的位置（记作 i）。  
> 7:再从最左位置往右找直到找到一个大于基准数的值，记录下该值的位置（记作 j）。  
> 8: 如果位置i<j，则交换i和j两个位置上的值，然后继续从(j-1)的位置往前和(i+1)的位置往后重复上面比对基准数然后交换的步骤。  
> 9:如果执行到i==j，表示本次比对已经结束，将最后i的位置的值与基准数做交换，此时基准数就找到了临界点的位置k，位置k两边的数组都比当前位置k上的基准值或都更小或都更大。  
> 10:上一次的基准值7已经把数组分为了两半，基准值7算是已归位（找到排序后的位置）。  
> 11:通过相同的排序思想，分别对7两边的数组进行快速排序，左边对\[left, k-1\]子数组排序，右边则是\[k+1, right\]子数组排序。  
> 12:利用递归算法，对分治后的子数组进行排序。  
> 13:快速排序之所以比较快，是因为相比冒泡排序，每次的交换都是跳跃式的，每次设置一个基准值，将小于基准值的都交换到左边，大于基准值的都交换到右边，这样不会像冒泡一样每次都只交换相邻的两个数，因此比较和交换的此数都变少了，速度自然更高。当然，也有可能出现最坏的情况，就是仍可能相邻的两个数进行交换。

**快速排序基于分治思想，它的时间平均复杂度很容易计算得到为O(NlogN)。**

三：代码实现

import java.util.Arrays;
    
    public class quicksort { 
        public static void swap(int[] arr,int i,int j){ 
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        public static int partion(int[] arr,int left, int right){ 
            int key=arr[left];
            int start=left;
            while (left<right){ 
                //一定要从后往前找第一个小于key的位置，否则数据的位置会产生错误
                while (left<right&&arr[right]>=key){ 
                    right--;
                }
                //从前向后找第一个大于key的数据位置
                while (left<right&&arr[left]<=key){ 
                    left++;
                }
                //交换
                swap(arr,left,right);
            }
            //把基准值和相遇的位置的数据进行交换
            //错误： arr[left] = key; 相遇位置的数据被覆盖
            swap(arr,left,start);
            return left;
    
        }
        public static void quickSort(int[] array,int left,int right){ 
            if(left<right){ 
                int mid =partion(array,left,right);//获取基准值在第一次排序后的下标位置
                quickSort(array,left,mid-1);//分为左右两个组再进行排序，递归
                quickSort(array,mid+1,right);
            }
    
        }
        public static void main(String[] args) { 
            int[] array={ 1,4,5,3,7,8,8,9};
            int left=0;
            int right=array.length-1;
            quickSort(array,left,right);
            System.out.println(Arrays.toString(array));
        }
    }