关于java:持续输出面试题之算法交换排序

开篇介绍

大家好，我是Java最全面试题库的提裤姐，明天这篇是数据结构与算法篇，次要介绍替换排序；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。

替换排序

两两比拟待排序记录的关键字，如果发现两个记录的秩序相同时即进行替换，直到没有反序地位。
分为冒泡排序和疾速排序。

冒泡排序

通过相邻元素之间比拟和替换，使较小移向顶部，从后往前两两比拟。
工夫复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳固

/** * 冒泡排序 * 循环比拟相邻的两个数，将较大的数放在前面 * * @param nums 待排序数值序列 */private static int[] bubbleSort(int[] nums) {    int len = nums.length;    if (len == 0 || len == 1) {        return nums;    }    for (int i = 0; i < len; i++) {        for (int j = 0, subLen = len - 1 - i; j < subLen; j++) {            if (nums[j + 1] < nums[j]) {                int tmp = nums[j + 1];                nums[j + 1] = nums[j];                nums[j] = tmp;            }        }    }    return nums;}

疾速排序

是冒泡排序的改良，比拟和替换从两端向两头进行。
过程：
设两个指针l和r，初值别离为low和high，基准为x=R[l]，首先从r地位开始向前搜寻第一个小于基准x.key的记录存入l所指地位上，l自增1，而后从l所指地位向后搜寻找到第一个大于基准x.key的记录存入r所指地位上，r自减1，反复直至l=r为止。

工夫复杂度：O(nlog2n)
空间复杂度：O(log2n)
稳定性：不稳固

public static void quickSort(int[] arr, int low, int high) {    int i, j, temp, t;    if (low > high) {        return;    }    i = low;    j = high;    //基准位    temp = arr[low];    while (i < j) {        //从左边开始，顺次往左递加        while (temp <= arr[j] && i < j) {            j--;        }        //从右边开始，顺次往右递增        while (temp >= arr[i] && i < j) {            i++;        }        //如果满足条件则替换        if (i < j) {            t = arr[j];            arr[j] = arr[i];            arr[i] = t;        }    }    //最初将基准为与i和j相等地位的数字替换    arr[low] = arr[i];    arr[i] = temp;    //递归调用左半数组    quickSort(arr, low, j - 1);    //递归调用右半数组    quickSort(arr, j + 1, high);}