复习数据结构：排序（三）——选择排序

Myth丶恋晨 2022-08-07 01:53 231阅读 0赞

选择排序的核心是：每趟选择最小的元素和首部交换。

时间复杂度：O(n^2)。

选择排序是一种不稳定的排序，为什么呢？因为不好处理相等两个数的前后位置，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。所以稳定排序是一定不会改变相等数之间之前位置关系的。

实现代码如下：

  1. #include<iostream>
  2. using namespace std; 
  4. void SelectSort(int a[], int n)
  5. {
  6.     for(int i = 0; i < n-1; i++)  // 注意到n-1
  7.     {
  8.         int minIndex = i+1; 
  9.         for(int j = i+1; j < n; j++)
  10.         {
  11.             if(a[j] < a[minIndex])
  12.                 minIndex = j;  // 选择i+1往后最小的数
  13.         }
  14.         if(a[minIndex] < a[i])
  15.             swap(a[minIndex], a[i]); 
  16.     }
  17. }
  19. int main()
  20. {
  21.     int a[] = {1, 6, 4, 3, 8, 2}; 
  22.     SelectSort(a, 6); 
  24.     for(int i = 0; i < 6; i++)
  25.         cout<<a[i]<<' '; 
  26.     cout<<endl; 
  28.     return 0; 
  29. }

参考链接：

http://blog.csdn.net/xiazdong/article/details/8462393

http://blog.csdn.net/hguisu/article/details/7776068

http://zhidao.baidu.com/link?url=zFcwJJZtDlBDx-5GK6\_4EVHMseEJg\_mWwNnPVAym4yPJk9YjYch3qpF\_-FSyKspp\_wxQZnS1UUzlpZxGhspHUK

发表评论

表情：
评论列表 （有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读