专栏首页为学选择排序法

选择排序法

选择排序法

分析

  • 假设已经给定了一个无序数组,现在需要将其按照一定顺序排好。现在我们使用选择排序法,每次从数组中选出一个最大的元素并将其与数组最后一个元素交换位置,使数组最后一个元素变为最大的。
  • 随着排序的进行,每次需要检查的元素数在逐渐减少,最后一次需要检查的元素都只有一个。既然如此,运行时间怎么还是O(*n*2)呢?这个问题问得好,这与大O表示法中的常数相关。第4章将详细解释,这里只简单地说一说。 你说得没错,并非每次都需要检查n个元素。第一次需要检查n个元素,但随后检查的元素数依次为n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n,因此运行时间为O(n × 1/2 × n)。但大O表示法省略诸如1/2这样的常数(有关这方面的完整讨论,请参阅第4章),因此简单地写作O(n × n)或O(*n*2)。 ​ — 《算法图解》

代码实现

C语言实现

因为C中对数组的删除比较麻烦,所以我没有按照《算法图解》中的思路每次选择最小的元素,而是选择了最大的。

void SelectionSort(int arr[], int length){  
    //C在函数中传数组长度较为麻烦,所以在数组定义出就将长度定义好传了过来

    int i, temp,biggest_index = 0;
    while (length){
         biggest_index = 0;
        for (i = 0; i < length; i++){
            if (arr[biggest_index] < arr[i]){
                biggest_index = i;
            }
        }
        printf("%d\n", arr[biggest_index]);
        temp = arr[biggest_index];
        arr[biggest_index] = arr[length - 1];
        arr[length -1] = temp;
        length --;
    }

}

JAVA语言实现

JAVA实现思路同C。

public int[] SelectionSort(int[] arr) {
        int length = arr.length;
        int biggestIndex;
        int i, temp;

        while(length > 0) {
            biggestIndex = 0;
            for(i = 0; i < length; i ++) {
                if(arr[biggestIndex] < arr[i]) {
                    biggestIndex = i;
                }
            }
            temp = arr[biggestIndex];
            arr[biggestIndex] = arr[length - 1];
            arr[length - 1] = temp;
            System.out.println(arr[length - 1]);
            length --;
        }
        return arr;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构常用预定义总结

    李志伟
  • 将Java EE应用程序部署到Docker Swarm集群

    Docker Swarm 为Docker提供本地集群。Docker Swarm 0.2.0版本的集群 提供了Docker Swarm 的基本介绍,以及如何创建一...

    李志伟
  • Java基础笔记整理---【07】面向对象程序设计-类和对象

    方法(函数): 返回值 方法名(参数类型 参数名称, ...){ 方法体(代码块) } this指调用的方法中(当前)的变量 类与对象 1.构造...

    李志伟
  • python 折行的正确姿势

    但是这个方案有个弊端,本来是一行字符串,结果变成了多行,而且如果有缩进的话,本来表示缩进的空格,也作为字符串的一部分了。跟我们实际想要的并不一致。

    用户2398817
  • leetcode非递归遍历二叉树

    flytam
  • Java 数组的基本操作

    遍历数组就是获取数组中的每个元素。通常遍历数组都是使用for循环来实现。 下面是遍历一个二维数组

    赵哥窟
  • Rxjava概念初识与学习路径推荐

    RxJava是使用Java实现的响应式编程库,RxJava即 Reactive Extensions Java。目前有两个版本RxJava1和RxJava2,推...

    爬蜥
  • LintCode-6.合并排序数组

    给出A=[1,2,3,4],B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]

    悠扬前奏
  • 让chrome插件在手机上跑起来

    创建一个chrome的插件,并让这个插件能够作为一个app,运行在终端设备上。 <!--more-->

    IMWeb前端团队
  • jQuery的 delegate问题

    支持为动态生成的标签元素绑定事件也许就live和delegate了吧,不过新版本已经不支持live了,只有delegate

    书童小二

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动