排序算法-一天两个之冒泡、选择排序

时间:2024-03-16 11:21:00

前言:

        准备笔试题中,这几天复习排序算法,尽量一天学一两个,并且以能手写代码的理解方式写出来。

冒泡排序:

思路:

首先,一定要先有一个场景,比如 1 3 9 5 4

现在想象它,从左到右,进行一次,注意是一次,两个两个比较,小的左边大的右边!

如1和3比,3和9比,9和5比(交换),9和4比(交换)

结果是:1 3 5 4 9

一次

for(j=0;j<len-1;j++){
  if(A[j]>A[j+1]){
    tem = A[j];
    A[j] = A[j+1];
    A[j+1] = tem;
  }
}

的结果就是这样(len是5嘛,由于是从0开始,所以截至是4,由是当前和下一个比较的,所以j<4, j最多到3,j+1等于4刚好就是访问到数组的最后一个)

这个明白了之后我们再观察1 3 9 5 4 ---->>1 3 5 4 9

发现9到了最高的地方,实际就是它每一轮的效果就是最大的那个会往上冒

例如现在是1 3 5 4 9 下一次必然5就会再倒数第二大的位置x x x 5 9

再下一次就是x x 4 5 9

再下一次就是x 3 4 5 9

(从这里可以看出,其实第一轮交换完之后就可以不用去比较次高位和9了,第二轮之后就不用比较次次高位和5了,以此类推,仔细看下面的for(j=0;j<len-1;j++)就优化了

因此呢,有5个元素,最多需要4轮上面的for循环就能完成排序,也就是0~len-1,所以完整的算法就是:

void bubble_sort(int *A,int len){
  int i,j,tem;

  for(i=0;i<len-1;i++)
   for(j=0;j<len-1-i;j++){

     if(A[j]>A[j+1]){
       tem = A[j];
       A[j] = A[j+1];
       A[j+1] = tem;
     }

    }
}

所以总结,冒泡排序的思想就是:

        每一轮都将 有且只有一个,那个最大的数,冒泡到右边去!

按照这个思路,我们就能明白每一行代码,每一个变量为啥这么写了。

交换排序:

思路:首先呢还是要有一个情景,比如 1 3 9 5 4

定一个min变量来标记最小的值,并且min会再每轮开始之前被赋值为i,比如第一轮,也就是说i代表的就是数组的第一个空位A[0],如果是第二轮,那i代表的就是数组的第二个空位A[1],每一轮,我们都要从整个数组中找出一个最小的来放到左边!

好现在开始想象第一轮!注意是第1轮,只进行一次!

现在min = 0,开始比较A[min]与3比较

1比3小,1比9小,1比5小,1比4小,好的,min = 0也就是数字1,获得了A[0]这个空位

再来,第二轮!

这个时候min =1开始比较A[min]与9比较

3比9小,3比5小,3比4小,好的,min = 1也就是数字3,得到了A[1]这个空位

再来,第三轮!

这个时候min = 2开始比较A[min]与5比较

9比5大(min记为5的下标),5比4大(min记为4的下标)

也就是说,最终min = 4的下标,也就是数组4得到了A[2]这个空位!

用代码写就是这样:

void swap_sort(int *A,int len){

    int i,j,min;    

    for(i=0;i<len;i++){

        min = i;

        for(j=i;j<len-1;j++){

            if(A[min]>A[j]) {min = j;} //找出这一轮里最小的那个数的角标

        }
        if(min!=i){//交换~

           tem = A[i];

           A[i] = A[min];

           A[min] = tem;

         }

    }

}

这两个排序算是简单的,后面等我复习了其他的再写吧~