算法-选择排序

Posted on | In |

介绍

分析

基本思想:

1
对n个记录进行扫描，选择最小的记录，将其输出，接着在剩下的n-1个记录中扫描，选择最小的记录将其输出，不断重复这个过程，直到只剩下一个记录为止，即可完成数据从小到大的排序过程

算法描述:

  1. 从数据中选择最小（或最大）的一个数据，然后将该数与第一个数交换
  2. 从剩下数据中选择最小（或最大）的一个数，然后将和第二个数进行交换
  3. 重复下去，直到只剩下一个数据为止
C实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 选择排序

 @param a 原数组
 @param len 数组长度
 */
void selectSort(int a[], int len)
{
    for (int i = 0; i < len - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        
        int temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

/**
 测试选择排序
 */
void testSelectSort()
{
    int arr[8] = { 19, 3, 10, 9, 16, 11, 28, 26 };
    int len = sizeof(arr)/ sizeof(arr[0]);
    
    printf("选择排序前:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    
    selectSort(arr, len);
    
    printf("\n选择排序后:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
Swift实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class SelectSort {
    
    /// 选择排序
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - len: 数组长度
    func selectSort(a: inout [Int], len: Int) {
        for i in 0..<len-1 {
            var minIndex : Int = i
            for j in i + 1..<len {
                if a[j] < a[minIndex] {
                    minIndex = j
                }
            }
            
            (a[i],a[minIndex]) = (a[minIndex],a[i])
        }
    }
    
    /// 测试
    func testSelectSort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("选择排序前:\(arr)", separator: " ")
        selectSort(a: &arr, len: arr.count)
        print("选择排序后:\(arr)", separator: " ")
    }
}

总结

时间复杂度:

  • 最差O(n^2)
  • 最优O(n^2)
  • 平均O(n^2)

空间复杂度:

  • O(1)

稳定性:

  • 不稳定