图解选择排序与插入排序

上一篇详述了冒泡排序及其优化,有兴趣的可以看看:如何优化冒泡排序?一、选择排序(SelectionSort)算法思想:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。排序过程:(默认升序)从原序列中找到最小值,与数组第一个元素交换;除第一个元素外,从剩下未排序的序列中找到最...

上一篇详述了冒泡排序及其优化,有兴趣的可以看看:

如何优化冒泡排序?

一、选择排序(SelectionSort)

  • 算法思想:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
  • 排序过程:(默认升序)
  1. 从原序列中找到最小值,与数组第一个元素交换;
  2. 除第一个元素外,从剩下未排序的序列中找到最小值,与数组第二个元素交换;
  3. 共N-1趟,每趟都找到未排序的最小值,放到已排序的序列后面。
![](https://img2018.cnblogs.com/blog/1603499/201904/1603499-20190415151538289-1047223683.jpg)

如图所示,每一趟找到未排序的最小值,并放到有序序列的后面(即当前趟对应于数组中的第几个元素)。

  • java实现选择排序
privatestatic<TextendsComparable<?superT>>voidselectionSort(T[]nums){
if(null==nums||nums.length==0){
thrownewRuntimeException("数组为null或长度为0");
}
intlength=nums.length;
intminValueIndex=0;
Ttemp=null;
for(inti=0;i<length-1;i ){
minValueIndex=i;
for(intj=i 1;j<length;j ){
if(nums[j].compareTo(nums[minValueIndex])<0){
minValueIndex=j;
}
}
if(minValueIndex!=i){
temp=nums[i];
nums[i]=nums[minValueIndex];
nums[minValueIndex]=temp;
}
}
}
  • 时间、空间复杂度及稳定性分析:
  1. 最好时间复杂度:最好情况是输入序列已经升序排列,需要比较n*(n-1)/2次,但不需要交换元素,即交换次数为:0;所以最好时间复杂度O(n^2)
  2. 最坏时间复杂度:最坏情况是输入序列是逆序的,则每一趟都需要交换。即需要比较n*(n-1)/2次,元素交换次数为:n-1次。所以最坏时间复杂度还是O(n^2)
  3. 平均时间复杂度:O(n^2)
  4. 空间复杂度:只用到一个临时变量,所以空间复杂度O(1)
  5. 稳定性:不稳定排序。如序列3,5,3,1。第一次交换结果为1,5,3,3,我们发现原序列的第一个3排在了第二个3的后面。

二、插入排序(InsertSort)

  • 算法思想:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

  • 排序过程:(默认升序)

    InsertionSort 和打扑克牌时,从牌桌上逐一拿起扑克牌,在手上排序的进程相同。

    举例:

    Input: {4, 3, 8, 5, 2, 6, 1, 7}。

  1. 首先拿起第一张牌, 手上有 {4}。

  2. 拿起第二张牌 3, 把 3insert 到手上的牌 {4}, 得到 {3 ,4}。

  3. 拿起第三张牌 8, 把 8 insert 到手上的牌 {3,4 }, 得到 {3 ,4,8}。

  4. 以此类推。

    插入排序由N-1趟排序组成。对于p=1到N-1趟排序后,插入排序保证从位置0到位置p上的元素为已排序状态。即插入排序利用了从位置0到p-1位置上已经有序的条件,将位置p上的元素向前查找适当的位置插入此元素。

    ![](https://img2018.cnblogs.com/blog/1603499/201904/1603499-20190415151611175-1026850390.jpg)

    如图所示:在第p趟,我们将位置p上的元素向左移动,直到它在前p 1个元素(包括当前位置的元素)中的正确位置被找到。

  • java实现插入排序

    privatestatic<TextendsComparable<?superT>>voidinsertSort(T[]nums){
    if(null==nums||nums.length==0){
    thrownewRuntimeException("数组为null或长度为0");
    }
    intlength=nums.length;
    Ttemp=null;
    inti=0;
    for(intp=1;p<length;p ){
    temp=nums[p];
    for(i=p;i>0&&(temp.compareTo(nums[i-1])<0);i--){
    nums[i]=nums[i-1];
    }
    nums[i]=temp;
    }
    }
  • 时间、空间复杂度及稳定性分析:

  1. 最好时间复杂度:最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需n-1次即可。即最好时间复杂度O(n)
  2. 最坏时间复杂度:最坏情况就是,序列是降序排列,那么总共需要n(n-1)/2次比较;移动次数(赋值操作)是比较次数减去n-1次(因为每一次循环的比较都比赋值多一次,共n-1次循环),即n(n-1)/2 - (n-1);所以最坏时间复杂度O(n^2)
  3. 平均时间复杂度:O(n^2)
  4. 空间复杂度:只用到一个临时变量,所以空间复杂度O(1)
  5. 稳定性:稳定。

三、总结

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。选择排序最好、最坏时间复杂度都为O(n^2),空间复杂度为O(1),属于不稳定排序。

插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千;或者若已知输入元素大致上按照顺序排列,那么插入排序还是一个不错的选择。插入排序最好时间复杂度为O(n)、最坏时间复杂度为O(n^2),空间复杂度为O(1),属于稳定排序。

源文地址:http://www.guoxiongfei.cn/cntech/14845.html
0