排序（四）之快速排序指针交换法

阳光穿透心脏的1/2处 2022-05-13 08:50 170阅读 0赞

在上一节讲的填坑法基础上，再修改一下，指针交换法的原理是，也是先移动右指针，找到一个符合条件的元素，再移动左指针，找到一个符合条件的元素，，右指针找到的是比基准元素小的，左指针找到的是比基准元素大的，然后将两个指针指向数据进行交换，然后再继续移动右指针，然后左指针，直到两个指针重合，把基准元素与两个指针重合时的元素交换，然后再递归循环。

代码如下：   用递归实现

package com.xhx.sort;
    
    
    import org.junit.Test;
    
    import java.util.Arrays;
    
    /**
     * 指针交换法，递归
     */
    
    public class App2 {
    
    
        @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;
            int right = endIndex;
    
            while (right > left) {
                //右指针循环左移
                while (left < right && arr[right] > pivot) {
                    right--;
                }
    
                //左指针循环右移
                while (left < right && arr[left] <= pivot) {
                    left++;
                }
                if(left<right){
                    int tem = arr[left];
                    arr[left] = arr[right];
                    arr[right] = tem;
                }
    
            }
            //基准位置与重合时left与right交换
            int tem = arr[left];
            arr[left]  = arr[startIndex];
            arr[startIndex] = tem;
    
    
            quickSort(arr, startIndex, left - 1);
            quickSort(arr, left + 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/bef428985947429da4ff8de6ae4c1711.png