天使漫步IT工作室天使漫步IT工作室

【算法基础】冒泡排序与选择排序<二>

上一节中,给大家讲了经典的冒泡排序,详细请点击冒泡排序与选择排序<一>。这一篇文章将会给大家讲一下和冒泡排序比较类似的选择排序。

一、选择排序

很多人刚接触到选择排序的时候,笔者认为这是冒泡排序的改良版,其实不然,其排序的思想和冒泡排序有很大不同,而且在编码方面也略有不同,而且在变量的内存读写方面,选择排序更有优势。

(1)选择排序的基本思想:
  • 1、从一个无序的序列中选择一个最小的数字(或者最大,看你排除的序列是升序还是降序)。
  • 2、将最小的数字和未排的无序序列中最前面一个数进行交换。
  • 3、每一趟排序都会确定其中一个数的位置,下一趟排序会从确定位置的下一个位置开始,直到该无序序列有序。
(2)选择排序举例:

假如有无序数组为 [2,3,1,4,5]

  • 第一趟:选择最小的数字为1,然后和未排序部分的排头位置进行交换:

此时就有已经确认的部分和未确定的部分,表示为:[1]+[3,2,4,5]

其中[3,2,4,5]是未排序部分。

  • 第二趟:选择数字最小的2 和 未排序部分的排头进行交换,即2 和 3 进行位置交换,此时就有:[1,2]+[3,4,5]

聪明读者已经发现该数组已经排序成功,然而程序没办法发现剩下的部分已经排好序(如果一个有序的数组进行排序,但是排下来发现原来已经排好了,这就是最坏的情况)。

  • 第三趟:选择最小的数3 和 3的位置进行交换,此时就有:[1,2,3]+[4,5]
  • 第四趟:选择最小的数4 和 4的位置进行交换,此时就有:[1,2,3,4]+[5]
  • 第五趟:选择最小的数5 和 5的位置进行交换,此时就有:[1,2,3,4,5]

注:第五趟在程序中不需要进行,实际上只进行了四趟的排序。

可以看到选择排序的基本思想:给定数组:int[] arr={里面n个数据};第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换;第2趟,在待排序数据arr[2]~arr[n]中选出最小的数据,将它与r[2]交换;以此类推,第i趟在待排序数据arr[i]~arr[n]中选出最小的数据,将它与r[i]交换,直到全部排序完成。

(3)选择排序代码实现:
         int[] arr = {2,3,1,4,5}; 
        //选择排序的优化
        for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序,总次数为 arr.length - 1 趟
            int k = i;
            for(int j = k + 1; j < arr.length; j++){//在未排序的部分中选最小的记录
                if(arr[j] < arr[k]){  //比较大小
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
            if(i != k){  //交换a[i]和a[k],位置不一样才交换,虽然也可以不判断,但是判断后会减少三个操作
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }    
        }

上面的代码可以看出相比于冒泡排序,减少了交换操作的次数,不过代码也多了一个逻辑。

(4)选择排序时间复杂度:

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0。当序列反序时,移动次数最多,为3N (N - 1) / 2。

所以,综上,简单排序的时间复杂度为 O(N2)。

到此,我们已经把选择排序给讲完。

本站原创,欢迎转载,转载敬请标明出处:天使漫步IT工作室 » 【算法基础】冒泡排序与选择排序<二>
添加新评论