交换类排序法(Java实现)
交换类排序算法总结
冒泡排序
冒泡排序是众多排序算法中最简单的一个,也是在学校最先学的一个排序算法。
冒泡排序的基本思路:从前两个元素开始依次比较相邻的两个元素,如果第一个比第二大则交换两个元素的位置,直到n-1次完成排序(n是数组的长度)。
可以使用一个int型变量记录一次循环的元素交换次数,如果为0则完成排序可以直接return
时间复杂度O(N2)
代码实现:
/**
* @author MaxYang
* @date 2021/7/21 1:50 下午
*/
public class BubbleSort {
public static void sort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
//创建数组
int nums[] = {1, 5, 8, 2, 3, 7, 9, 4, 6};
//调用排序方法
sort(nums);
//输出排序后的数组
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]);
}
}
}
快速排序
快速排序是基于二分的思想,对冒泡排序的一种改进。
快速排序的基本思路:假设现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这组数字里随便找一个数作为基准数。接下来的实现将会一第一个数6作为基准数,然后将这组数字中比基准数6大的放在6的右边,比基准数6小的放在6的左边。
排序算法
大致排序方法为分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“嗅探”,先从右往左找一个小于6的数,再从左往右找一个大于6的数字,然后交换这两个数字的位置。这里可以设置两个变量i和j,分别指向序列的最左边(i=0)和最右边(j=9)。
因为此时设置的基准数是最左边的数,所以必须让j先开始移动(否则交换完成时不能保证所有左边的值小于基准数),j一步一步向左挪动(j–),直到指向一个小于6的数时停下来。接下来i开始一步一步向右边移动(i++),直到找到一个大于6的数停下来。最后j停留在了数字5,i停留在了数字7。
现在i和j所指向的元素交换位置,交换后的序列如上图所示。
至此第一次交换结束。接下来j继续开始向左移动(记住依然是必须j先开始移动),遇到4(比6小)时停下来。然后i开始向右移动,到9时停下来(比6大)。此时再次将i和j指向的元素进行交换,交换后的序列如下:
至此第二次交换结束,开始第三次“嗅探”。j继续向左移动,发现3(比6小)后停了下来。i继续向又移动,这时在3的位置与j相遇。说明本次“嗅探”结束。将基数6和3进行交换,交换后的序列如下:
第一轮“嗅探”结束后,此时以基数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。以6为分界点拆分出了两个序列。左边序列是“3 1 2 5 4”,右边序列是“9 7 10 8”。接下来可以用上面同样的方式来处理这两个序列。
以6左边的序列为例:左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。按照上述方法排序得到的顺序应该是:
2 1 3 5 4
然后再对3左边的序列“2 1”和右边的序列“5 4”用同样的方法进行排序。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,此时序列“1”只有一个数不再需要进行任何处理。序列“5 4”结果同样的处理后最后可以得到如下序列:
1 2 3 4 5 6 9 7 10 8
对于6右边的“9 7 10 8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终得到如下序列:
1 2 3 4 5 6 7 8 9 10
到此为止排序完全结束。
快速排序之所以比较快是因为对比冒泡排序每次交换是跳跃式的,总交换次数少了很多。
在最坏的情况下时间复杂度和冒泡排序相同:O(N2),平均时间复杂度O(NlogN)
代码实现:
/**
* @author MaxYang
* @date 2021/7/21 11:58 下午
*/
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
//temp:基准数
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);
}
public static void main(String[] args) {
//创建数组
int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
//调用快速排序
quickSort(arr, 0, arr.length - 1);
//输出排序后的数组
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
支持一波