基础算法-直接选择排序

墨蓝 2022-07-28 01:08 156阅读 0赞

# 原理 #

直接选择排序也分为有序区和无序区，通过每一次比较得到无序区的最小元素放到有序区，直到无序区没有元素。

# 步骤 #

1 对于序列\{a1, a2, a3, a4… an\}我们分别划分成两个区域，无序区\{\}和有序区\{a1, a2, a3, a4… an\}。

2 得到无序区的最小元素ax，放到有序区\{ax\}，判断无序区\{a1, a2, … a(x-1), a(x+1)…an\}是否还有元素，如果有则继续步骤2；没有则终止。

# 实现 #

// 直接版本
    void swap(int *pa, int *pb) {
            int tmp = *pa;
            *pa = *pb;
            *pb = tmp;
    }
    void selectSort(int a[], int n) {
            for (int i = 0; i < n; ++i) {
                    int min = a[i];
                    for (int j = i+1; j <  n; ++j) {
                            if (min > a[j]) {
                                    swap(a+i, a+j);
                                    min = a[j];
                            }
                    }
            }
    }

// 更好的版本
    void swap(int *pa, int *pb) {
            int tmp = *pa;
            *pa = *pb;
            *pb = tmp;
    }
    void selectSort(int a[], int n) {
            for (int i = 0; i < n; ++i) {
                    int min = i;
                    for (int j = i+1; j <  n; ++j) {
                            if (a[min] > a[j]) { // compare: O(n^2)
                                    min = j;
                            }
                    }
                    swap(a+i, a+min); // swap: O(n)
            }
    }

# 时空复杂度 #

空间复杂度：O(1)  
时间复杂度：O(n^2),其中compare的次数为n-1, n-2, …. , 2, 1 = (n-1)n/2，所以可以计算需要compare为O(n^2)，swap次数为O(n),因此确定直接选择排序的时间复杂度为O(n^2)。