排序算法主要分为10大类，他们的优缺点主要体现在时间复杂度和空间复杂度上，还有代码的难易程度上

这里我主要是对快速排序做一个再理解，因为在学习快速排序的时候遇到了一些问题，这些问题真的是很容易让人掉头发

快速排序的基本实现逻辑

在待排序数组中找一个基值，将比这个基值小的值移动到基值左边，将比这个基值大的值移动到基值右边，然后再将基值左右两边的数据重复次操作（递归），最后就能得到有序的一组数据

虽然听起来比较简单，但是我在理解的时候还是花费了一些时间

举一个例子



    
        这是一个初始的数组：-10,20,15,1,0,30,-78,62,50
    

    
        假设我们就取中间值0作为基值那么经过一次排序之后：-10,-78,0,1,20,15,30,62,50 (大概就是这种)
    

    
        然后再将基值左边的数{-10,-78}进行操作：-78,-10
    

    
        然后再将基值右边的数{1,20,15,30,62,50}进行操作：1, 15, 20, 30, 62, 50
    

    
        ...
    

    
        最后得到：-78, -10, 0, 1, 15, 20, 30, 50, 62

这里面需要注意的点，我就是在这里被坑了，这里的基值不一定是中间值，你随便在数组中找一个来当做基值都可以，只不过找中间值的话可能更好理解（我并不觉得）

代码实现



    
        package com.quiteStore;
    

    
        
    

    
        import java.util.Arrays;
    

    
        
    

    
        public class QuiteStore {
    

    
         public static void main(String[] args) {
    

    
         int[] array = new int[]{-10,20,15,1,0,30,-78,62,50};
    

    
        
    

    
         QuikeSote.sote(array,0,array.length-1);
    

    
        
    

    
         }
    

    
        }
    

    
        
    

    
        //找到一个中间值（比较值）比较中间值两边值的大小将小的值放在左边，将大的值放在右边，一次进行这样的操作
    

    
        
    

    
        class QuikeSote{
    

    
        
    

    
         public static void sote(int[] array,int left,int right){
    

    
        
    

    
         //找到中间值（基值）
    

    
        
    

    
         int medianIndex = (left + right) / 2;
    

    
         int median = array[medianIndex];
    

    
         int temp = 0;
    

    
         //比较两边值的大小，从左边找到一个大的值，右边找到一个小的值，将这两个值交换，
    

    
         //特殊情况：左边的值都是小的，右边的值都是大的，此时就找完一轮
    

    
        
    

    
         while(left < right){
    

    
         while(array[left]<median && left <= right){
    

    
         left++;
    

    
         }
    

    
        
    

    
         //出循环说明找到了>=median的值
    

    
        
    

    
         while(array[right]>median && left <= right){
    

    
         right--;
    

    
         }
    

    
        
    

    
         //出循环说明找到了<=median的值
    

    
        
    

    
         //如果左下表和右下标相遇说明这一轮已经找完，那么就将基值和左下标或右下标对应的值进行交换，因为有一种特殊情况会使得基值发生改变
    

    
         //如果没有特殊情况交换之后也没事，因为左右下标所对应的值就是基值
    

    
        
    

    
         if(left>=right){
    

    
         temp = array[left];
    

    
         array[left] = median;
    

    
         median = temp;
    

    
         break;
    

    
         }
    

    
        
    

    
         //交换两个值
    

    
        
    

    
         temp = array[left];
    

    
         array[left] = array[right];
    

    
         array[right] = temp;
    

    
        
    

    
         //将右下标前移一位，因为右下标对应的值就是median，没必要进行再次比较，可能出现死循环
    

    
        
    

    
         if(array[left] == median){
    

    
         right--;
    

    
         }
    

    
        
    

    
         //将右下标前移一位，因为左下标对应的值就是median，没必要进行再次比较，可能出现死循环
    

    
        
    

    
         if(array[right] == median){
    

    
         left++;
    

    
         }
    

    
         System.out.println(Arrays.toString(array));
    

    
         //左递归
    

    
        
    

    
         QuikeSote.sote(array,0,left-1);
    

    
        
    

    
         //右递归
    

    
        
    

    
         QuikeSote.sote(array,right+1, array.length-1);
    

    
         }
    

    
         }

从执行图中也可以看出

最后哪一行就是最终结果

Java快速排序

快速排序的基本实现逻辑

举一个例子

代码实现