大家好，我是Java最全面试题库的提裤姐，今天这篇是数据结构与算法篇，主要介绍交换排序；在后续，会沿着第一篇开篇的知识线路一直总结下去，做到日更！如果我能做到百日百更，希望你也可以跟着百日百刷，一百天养成一个好习惯。
交换排序两两比较待排序记录的关键字，如果发现两个记录的次序相反时即进行交换，直到没有反序位置。
分为冒泡排序和快速排序。
通过相邻元素之间比较和交换，使较小移向顶部，从后往前两两比较。
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
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);
}
