排序（三）之快速排序填坑法

迈不过友情╰ 2022-05-13 05:24 150阅读 0赞

快速排序，采用分治法思想，开始选一个基准元素（默认第一个，也是第一个坑的位置），然后一个左指针，一个右指针，开始右指针向左移动，遇到比基准元素小的停下，放到坑的位置，这个元素的位置就成了新的坑，，然后左指针开始向右移动遇到比基准元素大的停下，把元素放入刚才新的坑的位置，这个位置又成了新的坑，，然后再移动右指针....然后再移动左指针...当两个指针重合时，最后一个坑的位置填入基准元素，最终比基准元素小的在左侧，比基准元素大的在右侧，依次循环递归下去。

package com.xhx.sort;
    
    
    import org.junit.Test;
    
    import java.util.Arrays;
    
    /**
     * 填坑法，递归
     * 基准元素默认选地一个，先移动右指针，再移动左指针，
     * 每找到一个元素，就把它放入坑中，这个元素的位置就变成了新的坑的位置
     *，然后再换另一测指针移动
     */
    
    public class App {
    
    
    
        @Test
        public void testQuickSort(){
            int[] array = {1,0};
            quickSort(array,0,array.length-1);
            System.out.println(Arrays.toString(array));
    
        }
        public void quickSort(int[] arr, int startIndex, int endIndex){
            if(startIndex>=endIndex){
                return;
            }
    
            //基准位置默认地一个元素
            int pivot = arr[startIndex];
            int left = startIndex+1; //这里+1了，下面的while都应该加上=条件，否则两个元素就出问题了
            int right = endIndex;
            //要填的坑的位置
            int index = startIndex;
    
            while (right>=left) {
                //右指针循环左移
                while (left <= right) {
                    if (arr[right] <= pivot) { //遇到比基准元素小的，填入坑的位置，移动左指针
                        arr[index] = arr[right];
                        index = right;
                        left++;
                        break;
                    }
                    right--;
                }
    
                //左指针循环右移
                while (left <= right) {
                    if (arr[left] > pivot) { //遇到比基准元素大的，填入坑的位置，移动右指针
                        arr[index] = arr[left];
                        index = left;
                        right--;
                        break;
                    }
                    left++;
                }
            }
            //把开始定义的基准元素填入坑，pivot左侧就是小的，右侧就是大的，index就是分割点
            arr[index]=pivot;
    
            quickSort(arr,startIndex,index-1);
            quickSort(arr,index+1,endIndex);
    
        }
    }

实时内容请关注微信公众号，公众号与博客同时更新：程序员星星

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzMjY0NjI_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzMjY0NjI_size_16_color_FFFFFF_t_70]: /images/20220513/4a2a67dea3e84ea390e5914620723581.png