数据结构与算法 基础排序(O(n^2))
数据结构与算法 基础排序(O(n^2))
选择排序
1592391606(1).jpg
1. 选择排序思想：
- 开始将i=0，作为最小值minIndex开始
- 与剩下的所有值比较
- 如果比minIndex对应位置的值还小，交换位置
- 当minIndex与后面所有的值比较后，此时minIndex对应的值就是最小值
- 将minIndex与 i(表示现在排序到那个位置) 交换位置
2. 代码实现
public static void selectSort(int[] arr){
if(arr.length==0)
return;
for(int i=0;i<arr.length;i++){
int minIndex=i;
for(int j=i+1;j<arr.length;j++){
//> 升序 < 降序
if(arr[minIndex]>arr[j]){
//1.易错点
minIndex=j;
}
}
swap(arr,minIndex,i);
}
}
//固定代码
public static void swap(int[] arr,int i,int j){
//1. 取出arr[i]的值
int temp=arr[i];
//2. j位置的值覆盖到i位置，此时i位置的值已经不存在了
//所以我们要在步骤1 将i对应的值保存起来
arr[i]=arr[j];
//3. j位置赋值temp temp其实保存的是i原来位置的值
//完成交换
arr[j]=temp;
}3. 易错点
不能直接找到一个比minIndex小的就swap，因为交换后比较的就是minIndex和后一个元素2个元素的比较 而不是minIndex和后面所有元素比较
4. 复杂度分析
首先有2层循环： 第一层，从0-length依次选取待排序的元素 第二次，将待排序的元素与后面的所有元素比较，选择后面所有元素中最小的元素，然后交换
所以时间复杂度为 O(n^2) 没有开辟新的空间，所以空间复杂度为O(1)
插入排序
插入排序.png
1. 插入排序思想：
- 首先认为一个元素就是有序的
- 那么排序时看第二个元素与前一个元素比较
- 如果小于前一个元素，那么交换位置，否则位置不变，此时i之前的所有元素都是有序的
- 主要思想是定义i之前的元素都是有序，那么只需要将i这个元素往前(往左)遍历找到i的位置，那么前i个元素就是有序的
2. 代码实现
public static void insertSort(int[] arr){
//1. i=1
for(int i=1;i<arr.length;i++){
//2. j>0
for(int j=i;j>0;j--){
//3. arr[j]<arr[j-1]
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}
}
}
//swap 代码同上 下面全部省略 默认arr是合法的3. 易错点
- i是从1开始的，也就是说arr.length如果排序至少有2个元素，如果只有一个元素那么本身就是有序的
- j>0 而不是j>=0,如果j>=0,那么j-1=-1 index=-1是违法的
- arr[j]<arr[j-1] 而不是arr[i]<arr[j-1].从上图中我们也知道，比较的arr[i]的值所在的位置是随着j的变化而变化的。如果使用arr[i]<arr[j-1]，当第一次交换后，i所在的位置已经与j-1位置的值交换了，那么就不是当时我们要比较的值了。
易错点3，不容易理解，要记住。
4. 优化
优化一：
public static void insertSort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}else{
break;
}
}
}
}从代码中我们看出，当i找到合适的位置后，我们没有退出循环，但是从图片上，此时已经是有序的了。所以用break直接跳出循坏。
优化二：
减少重复赋值
View绘制6步分析-1.png
思想时不变的，只不过将swap()换成单次赋值，这样减少一次赋值
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//1.
int temp = arr[i];
int j;
for (j = i; j > 0; j--) {
if (temp < arr[j - 1]) {
//2.
arr[j] = arr[j - 1];
} else {
break;
}
}
//3.
arr[j] = temp;
}
}- 以为我是覆盖，所以将要比较的i的位置的值保存起来，否则在第一次覆盖后i本来是4结果是8，那么4这个值就不见了
- 核心优化，覆盖，而非交换
- 在找到合适的位置然后交换1次
==易错点==
根据上图覆盖的思想，很容易写出下面的代码：
public static void insertSort5(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int minIndex = i;
for (int j = i; j > 0 ; j--) {
if (temp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {
//TODO 错误 当i=1时 执行一次没有走到这个语句 变成了{8, 8, 2, 3, 1, 5, 7, 4}
minIndex = j;
break;
}
}
arr[minIndex] = temp;
}
}这个是不对的，不能保存临死的j，因为当i=1时 执行一次没有走到这个语句，那么后面的排序就全错了
优化三：
优化判断，其实也并非多大优化，就是更加整洁
public static void insertSort(int[] arr){
for(int i=0;i<arr.length;i++){
int temp=arr[i];
int j;
for(j=i;j>0&&temp < arr[j - 1];j--){
arr[j] = arr[j - 1];
}
arr[j]=temp;
}
}可以看到一个简单插入排序就可以有这么多的优化。
==选择排序与插入排序的比较==
选择排序从从头(i=0)开始向后遍历,每次找到length-i后面元素中的所有元素中的最小值。然后记录最小值的位置，当从i遍历到length结束后，交换minIndex和i的位置，此时i前面(包括i位置)的所有元素就都是有序的了 插入排序，正好与选择排序相反，思想有点像我们生活中的扑克牌，当你抓1张的时候，没有别的牌和他比较，那么他就是有序的，再来一张，比第一张牌小，那么它俩交换。第二章插入到i=0的位置。再抓第三张牌(i=2)后，先和第二张(i=1)比较，小于，交换，在和i=0比较，小于再交换，此时第三张牌之前的元素都是有序的。 所以选择排序是向后寻找，插入是向前寻找 选择排序是不稳定排序，插入排序是稳定排序
选择排序核心代码：
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[min] < arr[j]) {
min = j;
}
}
swap(arr,min,i);
}如果我有一段数组： 5 6 8 5 2 7
当i=0时 认为5是最小的 ，所以i=0与i=3比较 不满足arr[min] < arr[j] 当i=4时满足
那么i=0和i=4交换，所以 最后变成2 6 8 5 '5' 7看出选择是不稳定的。
插入排序
View绘制6步分析.png
当红色4之前的元素都排好序，此时带插入的元素为蓝色4，判断 arr[j] < arr[j - 1];不成立，位置不变。比较下一个元素5.所以插入是稳定
冒泡排序
冒泡排序，应该是大家接触的最早的排序算法之一了。
原始数据
1.png
第一轮循环
2.png
完成第一轮排序
3.png
第二轮循环
4.png
完成第二轮排序
5.png
思想：
每次从启示位置(i=0)开始，相邻的两个元素，两两比较，当右侧位置的值大于左侧位置的值，交换位置，否则位置不变，继续下次循环。
6.png
编码前的分析
- 可以看到一共8个元素，当循环第七轮的时候其实，剩下最后一个元素一点是有序的，所以外层循环len-1次
- 右边紫色部分已经是排好序的了，所以循环1次排好序1个，循环i次，排好序i个，那么内层比较循环次数为len-i-1
代码实现
public static void bubbleSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
//1.
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}==易错点==
- 这里看到每次都是从0位置开始的不可以写成下面这个样子
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//1.
for (int j = 1; j < arr.length - i - 1; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j, j - 1);
}
}
}
}这个咋一看好像是正确的，但是实际少排序一次，当i=0 那么arr.length - i - 1 = 7，那么最后一个元素是没有比较的，输出的结果为：
1 2 3 4 5 6 8 9 7上面的代码是向前比较，而冒泡排序之所以叫冒泡排序，就是要排序的值，向后比较，向后移动。感觉是在冒出来
- 注意编码前的分析循环次数
优化一
7.png
可以看到，当前面的元素已经是有序的了，但是我们还是会走完流程。我们可以记录最后交换位置时j的位置
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSroted=true;
for (int j = 1; j < arr.length - i - 1; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j, j - 1);
isSroted=false;
}
}
if(isSorted){
break;
}
}
}