直接选择排序算法

港控/mmm° 2021-10-06 14:00 381阅读 0赞

### **直接选择排序算法思想** ###

#### 无序数组a\[0…n-1\]，第一次从a\[0\]~a\[n-1\]中选取最小值，与a\[0\]交换，第二次从a\[1\]~a\[n-1\]中选取最小值，与a\[1\]交换，….，第i次从a\[i-1\]~a\[n-1\]中选取最小值，与a\[i-1\]交换，…..，第n-1次从a\[n-2\]~a\[n-1\]中选取最小值，与a\[n-2\]交换，总共通过n-1次，得到一个按关键字从小到大排列的有序序列· ####

#  #

#### 直接选择排序算法过程如下: ####

#### 给定n=7，数组a中的7个元素为\[8,3,2,1,7,4,6\] ####

*  初始状态 \[ 8 3 2 1 7 4 6\]
 *  第1次，数组a\[0..6\]中最小的数为a\[3\]=1，交换a\[3\]<->a\[0\]，交换结果\[ 1 3 2 8 7 4 6\]
 *  第2次，数组a\[1..6\]中最小的数为a\[2\]=2，交换a\[2\]<->a\[1\]，交换结果\[ 1 2 3 8 7 4 6\]
 *  第3次，数组a\[2..6\]中最小的数为a\[2\]=3，交换a\[2\]<->a\[2\]，交换结果\[ 1 2 3 8 7 4 6\]
 *  第4次，数组a\[3..6\]中最小的数为a\[5\]=4，交换a\[5\]<->a\[3\]，交换结果\[ 1 2 3 4 6 8 7\]
 *  第5次，数组a\[4..6\]中最小的数为a\[4\]=6，交换a\[4\]<->a\[4\]，交换结果\[ 1 2 3 4 6 8 7\]
 *  第6次，数组a\[5..6\]中最小的数为a\[6\]=7，交换a\[6\]<->a\[5\]，交换结果\[ 1 2 3 4 6 7 8\]

#### 排序完成。 ####

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

##### **在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n\*n - n)/2，时间复杂度O(n^2)。直接选择排序为原地排序，空间复杂度O(1)。直接选择排序不是稳定的排序算法。** #####

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

### **算法实现** ###

#### 直接选择排序算法伪代码 ####

//直接排序
    SELECTION_SORT(A)
    {
      for i=1 to n-1
          min=i
          for j=i+1 to n
              if A[min] > A[j]
                 min = j
          swap A[min] <-> A[i]
    }

### **Test** ###

#### 用直接选择排序算法对数组arr\[10\] = \{8, 5, 10, 12, 7, 6, 15, 9, 11, 3\}从小到大排序。 ####

@Test
        public void sort3() {
            Integer arr[] = { 8, 5, 10, 12, 7, 6, 15, 9, 11, 3 };
            for (int i = 0; i < arr.length; i++) {
                int temp = arr[i];
                int min = arr[i];
                int key = i;
                for (int j = i; j < arr.length; j++) {
                    key = arr[j] < min ? j : key;
                    min = arr[j] < min ? arr[j] : min;
                }
                if (key != i) {
                    arr[i] = arr[key];
                    arr[key] = temp;
                }
            }
            // 输出数组元素
            for (Integer it : arr) {
                System.out.print(it + " ");
            }
        }

#### 输出 ####

3   5   6   7   8   9   10   11   12   15