算法-快速排序

快速排序1

以第一个数字6作为基数，使用双指针i,j进行双向遍历：

• 1、i从左往右寻找第一位大于基数（6）的数字，j从右往左寻找第一位小于基数（6）的数字；
• 2、找到后将两个数字进行交换。继续循环交换直到i>=j结束循环；
• 3、最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数（6）/基数（6）/大于基数（6）的三部分，即完成一趟快排；

package com.code.note.test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.locks.ReentrantLock;

public class Main {

    public void quickSort(int[] arr, int left, int right) {

        if (left >= right) return;

        int p = partition(arr, left, right);
        quickSort(arr, left, p - 1);
        quickSort(arr, p + 1, right);
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (arr[l] < pivot && l < r) {
                l++;
            }

            while (arr[r] > pivot && l < r) {
                r--;
            }
            swap(arr, l, r);
        }

        swap(arr, l, r);
        return r;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        Main m = new Main();
        int[] arr = {6, 5, 2, 7, 3, 9, 8, 4, 10, 1};
        m.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }
}

快速排序2

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（交换后index++，结束后返回index-1）。在这个分区退出之后，该基准就处于数列的中间位置（index-1）。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

package com.code.note.tree.quicksort;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

@Slf4j
public class Solution {

    public void quickSort(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        int partitionIndex = partition(arr, left, right);

        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);

    }

    private int partition(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);

        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        System.out.println("hello world");

        int[] arr = {4, 5, 1, 2, 3, 6, 7};
        Solution s = new Solution();
        s.quickSort(arr, 0, arr.length - 1);
        log.info(Arrays.toString(arr));
    }
}