排序-选择排序

雨点打透心脏的1/2处 2022-09-29 04:21 146阅读 0赞

## 1.简单选择排序前言 ##

--------------------

冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢？这就是选择排序法的初步思想。

选择排序的基本思想就是每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录。这里我们先介绍的是简单选择排序法。

--------------------

## 2.简单选择排序算法 ##

--------------------

**简单选择排序法(Simple Selection Sort)就是通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换之。**

/*对顺序表L作简单选择排序*/
    void SelectionSort(SqList *L)
    {
        int i,j,min;
        for(i=1; i<L->length; i++)
        {
            min = i;    /*将当前下标定义为最小值下标*/
            for(j=i+1; j<=L->length; j++)   /*循环之后的数据*/
            {
                if(L->r[min]>L->r[j])   /*如果有小于当前最小值的关键字*/
                    min = j;            /*将此关键字的下标赋值给min*/
            }
            if(i!=min)
                swap(L,i,min);          /*交换L->r[i]与L->r[min]的值*/
        }
    }

代码不难理解，针对排序的关键字序列是\{9,1,5,8,3,7,4,6,2\},对i从1循环到8。当i=1时，L.r\[i\]=9，min开始是1，然后与j=2到9比较L.r\[min\]与L.r\[j\]的大小，因为j=2时最小，所以min=2。最终交换了L.r\[2\]与L.r\[1\]的值。如下图所示，注意，这里比较了8次，却只交换数据操作一次。

![umsTtei.jpg][]

当i=2时，L.r\[i\]=9，min开始是2，经过比较后，min=9，交换L.r\[min\]与L.r\[i\]的值。如下图所示，这样就找到了第二位置的关键字。

![jMrHnGr.jpg][]

当i=3时，L.r\[i\]=5，min开始是3，经过比较后，min=5，交换L.r\[min\]与L.r\[i\]的值。如下图所示。

![FgUDQjS.jpg][]

之后的数据比较和交换完全雷同，最多经过8次交换，就可完成排序工作。

--------------------

## 3.简单选择排序的复杂度分析 ##

--------------------

从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要进行n-i次关键字的比较，此时需要比较n(n-1)/2次。而对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为O(n\*n)。

应该说，尽管与冒泡排序同为O(n\*n)，但简单选择排序的性能上还是略优于冒泡排序。

--------------------

## 4.简单选择排序的实现(Java) ##

--------------------

工程目录结构

![JIgZPct.png][]

简单选择排序类

package com.red.sort.selection;
    
    public class SelectionSort {
        public void selectionSort(int[] array) {
            for (int i = 0; i < array.length - 1; i++) {
                int temp = 0;// 记录临时值
                int min = i;// 用来保存最小值的索引
    
                // 寻找第i个小的数值
                for (int j = i + 1; j < array.length; j++) {
                    if (array[min] > array[j]) {
                        min = j;
                    }
                }
                if (i != min) {
                    // 将找到的第i个小的数值放到第i个位置上
                    temp = array[min];
                    array[min] = array[i];
                    array[i] = temp;
                }
    
            }
        }
    }

测试类

package com.red.sort.selection;
    
    public class Main {
        public static void main(String[] args) {
            SelectionSort selectionSort = new SelectionSort();
            int[] array = new int[] { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
            selectionSort.selectionSort(array);
            for (Integer i : array) {
                System.out.print(i + " ");
            }
        }
    
    }

输出结果：

1 2 3 4 5 5 6 7 8 9

--------------------

[umsTtei.jpg]: http://i.imgur.com/umsTtei.jpg
[jMrHnGr.jpg]: http://i.imgur.com/jMrHnGr.jpg
[FgUDQjS.jpg]: http://i.imgur.com/FgUDQjS.jpg
[JIgZPct.png]: http://i.imgur.com/JIgZPct.png