十大排序算法——选择排序及其优化_选择排序算法优化

1.学习方法：

记住原理很重要，把原理记住了，代码也就记住了

2.原理视频：

十大排序算法原理视频

3.原理简述：

n为排序数组长度，
循环n-1次，每次选择最大值索引，交换该索引的值和排序数组终点索引的值。

3.代码核心（两层for循环）：

第一层：控制排序数组的终点索引。

for (int i = array.size() - 1; i > 0; i--)
1

第二层：选择最大值索引。

int temp = j;
for (int j = 0; j < i; j++) {
    if (array[j] > array[temp]) temp = j;
}
1
2
3
4

最后一步，交换终点索引和最大值索引的值。

if (temp != i) swap(array[temp], array[i]);
1

4.普通选择排序代码：

  void select(vector<int> & array) {
        for (int i = array.size() - 1; i > 0; i--) {
            int temp = i; 
            for (int j = 0; j < i; j++) {
                if (array[j] > array[temp]) temp = j;
            }
            if (temp != i) swap(array[temp], array[i]);
        } 
    }
1
2
3
4
5
6
7
8
9

5.普通选择排序存在的问题：

每次排序都仅仅选出一个值，效率低。

6.优化——每次排序选出最大最小值：

注意点：

• 最大最小位置要在更新左右边界后进行更新
• 如果最大值索引是左边界索引，最小值索引不是左边界： 左边界索引的值 和 最小值索引的值 交换后，最大值索引的值此时在最小值索引处。需要对最大值索引进行更换。（不理解的可以举例推一下）

void select_optimize(vector<int> & array) {
        int l = 0, r = array.size() - 1; 
        while (l < r) {
            int max_p = r, min_p = l;
            for (int i = l; i <= r; i++) {
                if (array[i] > array[max_p]) max_p = i;
                if (array[i] < array[min_p]) min_p = i;
            }  
            if (min_p != l) swap(array[min_p], array[l]);
            if (max_p == l) max_p = min_p;//特殊情况处理
            if (max_p != r) swap(array[max_p], array[r]);
            r--;
            l++;  
        }  
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15