快速排序——一看就会，一写就废

深碍√TFBOYSˉ_ 2022-11-16 13:54 181阅读 0赞

### 快速排序 ###

*  原理：
 *  实现：
 *  partition
 *   *  hoare法：
     *   *  实现：
     *  挖坑法：
     *   *  实现：
     *  前后遍历：
     *   *  实现：
 *  非递归实现：

# 原理： #

1、从待排序区间中选择一个数，作为基准值（pivot）；  
2、Partition:遍历整个待排序区间，将小于等于基准值放在基准值左边，将大于等于基准值的放在基准值右边；  
3、采用分治思想，对左右两个区间相同方式处理，直到区间长度为1，代表有序，或者区间长度为0，代表没有数据。

# 实现： #

当我们看见使用相同的方式处理，应该很快想到需要使用递归，但是使用递归，我们需要划定区间，所以需要quickRange,（至于partition方法如何实现，我们暂时不考虑）

public class QuickSort { 
        public static void quick(int[] array) { 
            quickRange(array, 0, array.length - 1);
        }
    
        private static void quickRange(int[] array, int from, int to) { 
            int size = to - from + 1;
            if (size <= 1) { 
                return;
            }
            int pivotIndex = partition(array, from, to);
            quickRange(array, from, pivotIndex - 1);
            quickRange(array, pivotIndex + 1, to);
        }
    }

# partition #

那么我们如何实现partition的方法呢，如何将基准值左边都比基准值小，基准值右边都比基准值大呢？

## hoare法： ##

找到一个基准值（习惯性找第一个），然后从区间前后开始，当左边比基准值小，就继续，直到找到一个比基准值大的元素停下来。右边也是直到找到比基准值小的元素停下来，然后交换两个位置，继续走…直到最后，再将基准值和中间位置交换。

### 实现： ###

private static int partition(long[] array, int from, int to) { 
            int left = from;
            int right = to;
            long poivt = array[from];
            while (left < right) { 
                while (left < right && array[right] >= poivt) { 
                    right--;
                }
                while (left < right && array[left] <= poivt) { 
                    left++;
                }
                //交换
                Swap.swap(array, left, right);
            }
            Swap.swap(array, left, from);
            return left;
        }

## 挖坑法： ##

原理和Hoare法基本一致，唯一不同的就是，不进行交换，而是直接进行赋值（就想挖坑+填坑）

### 实现： ###

private static int partition(long[] array, int from, int to) { 
            int left = from;
            int right = to;
            long pivot = array[left];
            while (left<right){ 
                while (left<right&&array[right]>=pivot){ 
                    right--;
                }
                array[left] = array[right];
                while (left<right&&array[left]<=pivot){ 
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = pivot;
            return left;
        }

## 前后遍历： ##

选定一个基准值，从前到后遍历无序区间，如果遇到比基准值小的，则将比基准值小的区间后面加上一个。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

### 实现： ###

private static int partition3(long[] array, int from, int to) { 
            long pivot = array[from];
            int s = from + 1;
            for (int i = from + 1; i <= to; i++) { 
                if (array[i] < pivot) { 
                    Swap.swap(array, i, s);
                    s++;
                }
            }
            Swap.swap(array, s - 1, from);
            return s - 1;
        }

# 非递归实现： #

原理还是先处理基准值左边，在处理基准值右边，我们借助栈实现非递归过程：

public static void quickSort(long[] array) { 
            Stack<Integer> stack = new Stack<>();
            stack.push(array.length - 1);
            stack.push(0);
            while (!stack.isEmpty()) { 
                int left = stack.pop();
                int right = stack.pop();
                if (left >= right) { 
                    continue;
                }
                int pivotIndex = partition(array,left,right);
                stack.push(right);
                stack.push(pivotIndex+1);
    
                stack.push(pivotIndex-1);
                stack.push(left);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/b50acce267f74d37b6adda021b95fa5f.png