[数据结构与算法]Java排序算法

java在内存级别的排序

大致可以分成8类排序

冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序
桶排序

各种排序的时间复杂度

冒泡排序

思路：

每一次遍历将最大的那个放到没有排序好的最后,不满足采用交换的方式
比如：
第一次：将最大的数放到最后的位置
第二次：将 0 - （n-1）中最大的数放到 n-1的位置
…

假如排序的数为 : 5 , 2, -10, 3
第一次排序 ：
（1）2， 5， -10， 3 // 因为 2 小于 5 进行交换
（2）2， -10， 5， 3 // -10 小于 5进行交换
（3）2， -10， 3， 5 // 3 小于 5 进行交换
第一轮排序完：最大值5到最后


第二轮排序: 最后一个排好了 不需要排序
(1）-10， 2， 3， 5 // -10小于 2进行交换
(2）-10， 2， 3， 5 // 3 大于2无序排序
第二轮排序完：第二大的值放到了倒数第二位

第三轮排序：
(1）-10， 2， 3， 5 // 2 大于 -10 无序交换
第三轮排序完：就是有序的了

结论：
1、N 个 数需要排序 N - 1次
2、每一次排序都是找到那个区间中最大的值

public static int[] bubblingSort(int[] arr) {
    // 遍历 n - 1次
    for (int i = arr.length - 1; i > 0; i--) {
        // 临近的进行比较 如果不满足进行交换
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 进行交换
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

// 这里可以使用异或的方式
// 但是需要注意 i 和 j 之间的数不可以在同一个内存中
public static void swap(int[] arr, int i, int j) {
    // 使用异或的方式进行交换
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}
// 正常的交换
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

选择排序

思路：

每次找到最小的数放到相应的值
比如：
第一轮 ： 从 1 - n 中找到最小的值放到 1 号的位置
第二轮 : 从 2 - n 中找到最小的值放到 2 号的位置
…

public static int[] selectSort(int[] arr) {
    // 进行去掉不需要进行排序的数据
    if (arr == null || arr.length < 2) {
        return arr;
    }
    // 选择排序
    for (int i = 0; i < arr.length; i++) {
        // 将第一个值先比作最小的值 这个是假设
        int minIndex = i;
        // 再用一个for找到 i - n中最小的值进行交换
        for (int j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        // 到这里minIndex指向的就是最小的值
        // 进行交换 这里可以进行优化 只有不相同的时候再进行交换
        int temp = arr[j];
        arr[j] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

插入排序

思路

第一次保证 0 - 0 是有序的
第二次保证 0 - 1 是有序的
第三层保证 0 - 2 是有序的
第n层保证 0 - (n-1)是有序的
如果发现两个的顺序是不满足的，就进行交换

public static void insertSort(int[] arr) {
    // 插入排序
    // 因为 0-0默认就是有序的 不需要进行排序
    // 这一个for循环 每一次循环保证 0 - i 是有序的
    for (int i = 1; i < arr.length; i++) {
        // 第二次循环 保证是有序的
        // j代表当前数据的前一个数据
        for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
            // arr[j + 1] < arr[j] 说明后面的一个数小于前面的一个数
            // 进行交换
            swap(arr, j, j + 1);
        }
    }
}
public static void swap(int[] arr, int left, int right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}