算法每天一练

• 原理

取第一个元素作为参考值进行保存，比参考值大的放入右边，比参考值小的放入左边，依次类推，得到有序的数组

• 代码

package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] arr = {3,5,1,5,2,6,8,9,0,-1,4,6,7,9,0,-6,4,2,2,4,5,1,7};
        quickSort(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(v->System.out.println(v));
    }

    private static void quickSort(int[] arr, int min, int max) {
        if (max <= min) {
            return;
        }

        int num = arr[min];
        int left = min;
        int right = max;
        while (right > left) {
            for (int i=right; i>left&&right>left; i--) {
                if (arr[i] < num) {
                    arr[left ++] = arr[i];
                    break;
                }
                right --;
            }

            for (int i=left; ileft; i++) {
                if (arr[i] > num) {
                    arr[right --] = arr[i];
                    break;
                }
                left ++;
            }
        }
        arr[left] = num;
        quickSort(arr, min, left - 1);
        quickSort(arr, left + 1, max);
    }
}

• 原理

先弄一个大堆（父节点比子节点都大）

讲第一个元素和最后一个元素互换，并且把数组看成去掉最后一个元素的新数组，对新数组进行大堆恢复，依次类推，成为有序数组

• 代码

package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] arr = {3,5,1,5,2,6,8,9,0,-1,4,6,7,9,0,-6,4,2,2,4,5,1,7};
        heapSort(arr);
        Arrays.stream(arr).forEach(v->System.out.println(v));
    }

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

    private static void adjust(int[] arr, int index, int len) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;
        if (left < len && arr[largest] < arr[left]) {
            largest = left;
        }

        if (right < len && arr[largest] < arr[right]) {
            largest = right;
        }

        swap(arr, index, largest);

        if (index != largest) {
            adjust(arr, largest, len);
        }
    }

    private static void maxHeap(int[] arr, int len) {
        int half = len / 2;
        for (int i=half; i>=0; i--) {
            adjust(arr, i, len);
        }
    }

    public static  void heapSort(int[] arr) {
        int len = arr.length;
        maxHeap(arr, len);

        for (int i=len-1; i>=0; i--) {
            swap(arr, i, 0);
            adjust(arr, 0, --len);
        }
    }
}