内部排序算法:直接选择排序

基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:

  1. 初始状态:无序区为R[1..n],有序区为空。
  2. 第1趟排序:在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1] 交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  3. ……
  4. 第i趟排序:第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

算法实现

直接选择排序算法,Java实现,代码如下所示:

public abstract class Sorter {
     public abstract void sort(int[] array);
}

public class StraightSelectionSorter extends Sorter {

     @Override
     public void sort(int[] array) {
          int tmp; // 用于交换数据的暂存单元
          for (int i = 0; i < array.length - 1; i++) { // 这里只要从0~array.length-2即可
               int k = i;
               for (int j = i + 1; j < array.length; j++) { // 该循环可以找到右侧无序区最小的元素array[k]
                    if (array[k] > array[j]) {
                         k = j;
                    }
               }
               if (k != i) { // 如果array[i]不是无序区最小的,需要与无序区最小的进行交换
                    tmp = array[i];
                    array[i] = array[k];
                    array[k] = tmp;
               }
               // 如果array[i]是无序区最小的元素,不需要执行交换
          }
     }
}

直接选择排序算法,Python实现,代码如下所示:

class Sorter:
    '''
    Abstract sorter class, which provides shared methods being used by
    subclasses.
    '''
    __metaclass__ = ABCMeta

    @abstractmethod
    def sort(self, array):
        pass

class StraightSelectionSort(Sorter):
    '''
    Straight selection sorter
    '''
    def sort(self, array):
        i = 0
        length = len(array)
        while i<length -1:
            k = i
            j = i
            while j<length:
                if array[j]<array[k]:
                    k = j
                j = j + 1
            if k!=i:
                array[k], array[i] = array[i], array[k]
            i = i + 1

排序过程

首先,从0~n-1个元素中找到最小的元素,交换到0位置上;
其次,再从1~n-1中找到次最小的元素,交换到1位置上;
……;
最后从n-2~n-1中找到最小的元素,交换到n-2位置上。n-1位置上一定是最大的元素,所以总共进行n-1趟选择排序。
需要注意的是:
每次确定无序区后,其中除了第一个元素之外的其它元素(设为e)与第一个元素(设为E)比较,只有满足e<E的时候才需要交换一次。

排序过程示例如下:
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20。

  • 第1趟选择排序

从array[1,n-1]中找到最小的元素:
array[0] = 94>array[1] = 12,交换array[0]与array[1],即array[0] = 12array[2] = 34不成立,不交换;
array[0] = 12>array[3] = 76不成立,不交换;
array[0] = 12>array[4] = 26不成立,不交换;
array[0] = 12>array[5] = 9,交换array[0]与array[5],即array[0] = 9array[6] = 0,交换array[0]与array[6],即array[0] = 0array[7] = 37不成立,不交换;
array[0] = 0>array[8] = 55不成立,不交换;
array[0] = 0>array[9] = 76不成立,不交换;
array[0] = 0>array[10] = 37不成立,不交换;
array[0] = 0>array[11] = 5不成立,不交换;
array[0] = 0>array[12] = 68不成立,不交换;
array[0] = 0>array[13] = 83不成立,不交换;
array[0] = 0>array[14] = 90不成立,不交换;
array[0] = 0>array[15] = 37不成立,不交换;
array[0] = 0>array[16] = 12不成立,不交换;
array[0] = 0>array[17] = 65不成立,不交换;
array[0] = 0>array[18] = 76不成立,不交换;
array[0] = 0>array[19] = 49不成立,不交换。
此时数组状态如下:{0,94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。
此时,有序区为{0},无序区为{94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。

  • 第2趟选择排序

从array[2,n-1]中找到最小的元素:
array[1] = 94>array[2] = 34,交换array[1]与array[2],即array[1] = 34array[3] = 76不成立,不交换;
array[1] = 34>array[4] = 26,交换array[1]与array[4],即array[1] = 26array[5] = 12,交换array[1]与array[5],即array[1] = 12array[6] = 9,交换array[1]与array[6],即array[1] = 9array[7] = 37不成立,不交换;
array[1] = 0>array[8] = 55不成立,不交换;
array[1] = 0>array[9] = 76不成立,不交换;
array[1] = 0>array[10] = 37不成立,不交换;
array[1] = 9>array[11] = 5,交换array[1]与array[11],即array[1] = 5array[12] = 68不成立,不交换;
array[1] = 5>array[13] = 83不成立,不交换;
array[1] = 5>array[14] = 90不成立,不交换;
array[1] = 5>array[15] = 37不成立,不交换;
array[1] = 5>array[16] = 12不成立,不交换;
array[1] = 5>array[17] = 65不成立,不交换;
array[1] = 5>array[18] = 76不成立,不交换;
array[1] = 5>array[19] = 49不成立,不交换。
此时数组状态如下:{0,5,94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。
此时,有序区为{0,5},无序区为{94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。

  • 第3趟选择排序

排序后数组状态为:{0,5,9,94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。
此时,有序区为{0,5,9},无序区为{94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。

  • 第4趟选择排序

排序后数组状态变化:
{0,5,9,76,94,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49},
{0,5,9,34,94,76,26,37,55,76,37,12,68,83,90,37,12,65,76,49},
{0,5,9,26,94,76,34,37,55,76,37,12,68,83,90,37,12,65,76,49},
{0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49},
{0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49},
此时,有序区为{0,5,9,12},无序区为{94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}。
……

  • 第n-1趟选择排序

依此类推,执行n-1趟选择排序,最后得到:有序区为{0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90},无序区为{94},此时整个数组已经有序,n-1趟选择排序后,排序完成。

算法分析

  • 时间复杂度
  1. 记录比较次数:
  2. 无论待排序数组初始状态如何,都要进行n-1趟选择排序:

    • 第1趟:比较n-1次;
    • 第2趟:比较n-2次;
    • ……
    • 第n-1趟:比较1次。

    从而,总共的比较次数为:1+2+……+(n-1) = n(n-1)/2

  3. 记录移动次数:
  4. 如果待排序数组为正序,则记录不需要交换,记录移动次数为0;
    如果当排序数组为逆序,则:

    • 第1趟:交换1次,移动3次;
    • 第2趟:交换1次,移动3次;
    • ……
    • 第n-1趟:交换1次,移动3次。

    从而,总共的移动次数为:3(n-1) = 3(n-1)。
    因此,时间复杂度为O(n2)。

  • 空间复杂度

在选择排序的过程中,设置一个变量用来交换元素,所以空间复杂度为O(1)。

排序稳定性

选择排序是就地排序。
通过上面的排序过程中数组的状态变化可以看出:直接选择排序是不稳定的。

Creative Commons License

本文基于署名-非商业性使用-相同方式共享 4.0许可协议发布,欢迎转载、使用、重新发布,但务必保留文章署名时延军(包含链接:http://shiyanjun.cn),不得用于商业目的,基于本文修改后的作品务必以相同的许可发布。如有任何疑问,请与我联系

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>