基本排序算法总结
排序算法总结
1 选择排序
1.1 思路分析
① 在0~N-1 范围上找到最小值，将其放在0位置上； ② 在1~N-1 范围上找到最小值，将其放在1位置上； … 知道确定最后一个值的位置。
1.2 代码实现
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1 找到最小值，在哪，放到0位置上
// 1 ~ n-1 找到最小值，在哪，放到1 位置上
// 2 ~ n-1 找到最小值，在哪，放到2 位置上
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
// i ~ N-1 上找最小值的下标
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(i, minIndex,arr);
}
}
public static void swap(int i ,int j,int[] arr){
if (arr[i]==arr[j]){
return;
}
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
时间复杂度O(N^2);
空间复杂度O(1)
这里说明解释一下在交换两个数据位置时，为什么采用位运算，而且要判断一下交换值是否相等
当传递给swap函数的x和y相同时，不光值相同，它们的地址也相同，所以出现这种情况：a ^ a = 0；所以，在这里就会出错了！交换位置之后会发现值出现0 0的情况。
2 冒泡排序
2.1 思路分析
- 排序时判断当前位置与下一个位置的值大小，谁大谁往后，直到判断到N，这样一次循环下来之后确定最后一个值一定是待排序数组中的最大值；
- 再次从1开始判断与下一个位置的值做比较，谁大谁往后，直到判断到N-1，确定倒数第二个值的位置；
- 重复上面的过程，直到全部确定值的大小位置。
2.2 代码实现
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1
// 0 ~ N-2
// 0 ~ N-3
for (int i = arr.length -1;i > 0;i--){
for (int j = 0;j<i;j++){
if (arr[j]>arr[j+1]){
swap(j,j+1,arr);
}
}
}
}
交换函数依然还是上面的函数
时间复杂度O(N^2);
空间复杂度O(1);