算法整理

闲来无聊，整理了一下各种算法，还没更新完，先写这些吧。。。

选择排序

// 选择排序（Selection sort）是一种简单直观的排序算法。
// 它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
// 以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
public void SelectionSort(int arr[]) {
    if (arr.length == 0 || arr == null) {
        return;
    }
    //思路：获取最小的数，放在最前面
    int minIndex = 0;
    int temp = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                //获取到最小值的下标
                minIndex = j;
            }
        }
        //交换位置
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    for (int x : arr) {
        System.out.print(x + " ");
    }
}

---

冒泡排序

public void bubbleSort(int arr[]) {
    //冒泡排序算法的原理如下：
    //比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    //对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
    //针对所有的元素重复以上的步骤，除了最后一个。
    //持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
    if (arr.length < 2 || arr == null) {
        return;
    }
    //外层控制需要排序的趟数，内层循环控制 每趟相互比较的次数
    for (int i = 0; i < arr.length - 1; i++) {
        //由于每次比较都会把最大数，放入数组最后，所以每次比较会，i个数都不需要比较了
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                arr[j] = arr[j + 1] + arr[j];
                arr[j + 1] = arr[j] - arr[j + 1];
                arr[j] = arr[j] - arr[j + 1];
            }
        }
    }
    for (int x : arr) {
        System.out.print(x + " ");
    }
}

---

快速排序

/**
 * 快速排序
 *
 * @param arr
 * @param left
 * @param right
 */
public void quicksort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int init_left = left;
    int init_right = right;
    //以数组的第一个数为基准
    int start = arr[left];
    while (left != right) {
        //找到右边比左边小的数，交换位置
        while (left < right && arr[right] >= start) {
            right--;
        }
        //交换
        arr[left] = arr[right];
        arr[right] = start;
        //此时从左边开始，找到大于基准值的值，交换位置
        while (left < right && arr[left] <= arr[right]) {
            left++;
        }
        arr[right] = arr[left];
        arr[left] = start;
    }
    System.out.println("节点值：" + left);
    System.out.println("排序结果：");
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
    quicksort(arr, init_left, left - 1);
    quicksort(arr, right + 1, init_right);
}