当前位置：首页 > article >正文

【数据结构和算法实践-排序-快速排序】

article 2024/11/17 22:37:04

数据结构和算法实践-排序-归并排序

- 题目
- My Thought
- 代码示例
- - JAVA-8

题目

排序

My Thought

然后再进行递归，递归要注意两个方面：
一、自我调用
二、终止条件：即函数边界
注意点：树、递归*

代码示例

JAVA-8

  public class QuickSort {


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

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

        sort(arr, left, pivot - 1);
        sort(arr, pivot + 1, right);

    }

    private int partition(int[] arr, int left, int right) {
        int index = 0;
        int pivot = arr.length - 1;
        int less = -1;
        while (index < arr.length) {
            if (arr[index] < arr[pivot]) {
                swap(arr, ++less, index);
            } else {
                index++;
            }
        }
        return less;
    }


    /**
     * 用左右两个指针，进行交换
     *
     * @param arr
     * @param left
     * @param right
     */
    private void swap(int[] arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}