前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >直接选择排序算法

直接选择排序算法

作者头像
qubianzhong
发布2019-07-01 14:04:55
1K0
发布2019-07-01 14:04:55
举报
文章被收录于专栏:行者常至

直接选择排序算法思想

无序数组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)。直接选择排序不是稳定的排序算法。

算法实现

直接选择排序算法伪代码
代码语言:javascript
复制
//直接排序
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}从小到大排序。
代码语言:javascript
复制
    @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 + "   ");
        }
    }
输出
代码语言:javascript
复制
3   5   6   7   8   9   10   11   12   15   
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016年08月31日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
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]
          • 排序完成。
            • 在直接选择排序中,共需要进行n-1次选择和交换,每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动,因此,总的比较次数C=(n*n - n)/2,时间复杂度O(n^2)。直接选择排序为原地排序,空间复杂度O(1)。直接选择排序不是稳定的排序算法。
        • 算法实现
          • 直接选择排序算法伪代码
          • Test
            • 用直接选择排序算法对数组arr[10] = {8, 5, 10, 12, 7, 6, 15, 9, 11, 3}从小到大排序。
              • 输出
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档