文档章节

简单排序之-选择排序,冒泡,直接插入排序

写代码的奥特曼
 写代码的奥特曼
发布于 2017/07/20 11:57
字数 1838
阅读 21
收藏 0

先尝试用最简单的想法去实现排序,以此来比较学习冒泡排序

问题:设有一数组,其大小为10个元素(int   str[10])数组内的数据是无序。现在要求我们通过编程将这个无序的数组变成一个从小到大排序的数组(从下标为0开始)

思路:按照题目的要求,毫无疑问,正确的结果应该就像这样: 1 2 3 4 5 6 7 8 9 10   要做到这样,最简单和最直接想到的方法就是进行对比交换。

 

  • 首先,把10个数里最小的个数放到下标为0的位置上(str[0])
  • 通过将下标为0的数(str[0])与剩下其余9个数进行对比交换(将较少者放置在下标为0的位置上),就可以得到这10个数最小的那个
  • 10个数最小的那位确定后,接下来就要找剩下9个数最小的那个。
  • 因为已经确定出一个最小的数,所以就不要动str[0],直接从str[1]开始,与剩下的8个数对比交换,找出9个数中最小的那位放到下标为1(str[1])的位置上
  • 继续按照这个思路就可以将这十个数变成有序的(从小到大)的数组

代码:

#include <stdio.h>

void swap(int *a, int *b); //交换两个数

int main()
{
	int     str[10];
	int     i, j;
	//初始化数组为10 9 8 7 6 5 4 3 2 1
	for (i = 0; i < 10; i++)
	{
		str[i] = 10 - i;
	}
	//排序,从a[0]开始排,从小到大
	for (i = 0; i < 10; i++)
	{
		for (j = i + 1; j < 10; j++)
		{
			if (str[i] > str[j])
			{
				swap(&str[i], &str[j]);
			}
		}
	}
        //将十个数输出
	for (i = 0; i < 10; i++)
		printf("%d\n", str[i]);
	return    0;
}
void swap(int *a, int *b)
{
	int     c;
	 c = *a;
	*a = *b;
	*b =  c;
}

这个方法是比较容易想到的实现方法。但存在不足:就是本来位于前面的较小数被交换到后面

 

演示:

开始:9 4 5 6 8 3 2 7 10 1  (下标从左到右分别是0~9)按照上面的程序进行对比交换

第一次:4 9 5 6 8 3 2 7 10 1 

第二次:4 9 5 6 8 3 2 7 10 1 

。。。:(没有交换)

第五次:3 9 5 6 8 4 2 7 10 1 

第六次:2 9 5 6 8 3 4 7 10 1 

。。。:(没有交换)

第十次:1 9 5 6 8 3 4 7 10 2 

 

可以看出,原来较小的数是在前面的,经过一轮的交换后放到后面了

那么怎样解决这个不足呢?

引出我们最基础的三类算法:选择,冒泡,插入。

  先定义个交换数组元素的函数,供排序时调用

/**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

简单选择排序

简单选择排序是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。

  在算法实现时,每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小,交换是个比较耗时的操作。其实我们很容易发现,在还未完全确定当前最小元素之前,这些交换都是无意义的。我们可以通过设置一个变量min,每一次比较仅存储较小元素的数组下标,当轮循环结束之后,那这个变量存储的就是当前最小元素的下标,此时再执行交换操作即可。代码实现很简单,一起来看下。

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时,min用于存放较小元素的数组下标,这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标,避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换,如果min发生变化,则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

简单选择排序通过上面优化之后,无论数组原始排列如何,比较次数是不变的;对于交换操作,在最好情况下也就是数组完全有序的时候,无需任何交换移动,在最差情况下,也就是数组倒序的时候,交换次数为n-1次。综合下来,时间复杂度为O(n2)

 

冒泡排序

冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序

代码实现

    在冒泡排序的过程中,如果某一趟执行完毕,没有做任何一次交换操作,比如数组[5,4,1,2,3],执行了两次冒泡,也就是两次外循环之后,分别将5和4调整到最终位置[1,2,3,4,5]。此时,再执行第三次循环后,一次交换都没有做,这就说明剩下的序列已经是有序的,排序操作也就可以完成了,来看下代码 

/**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

根据上面这种冒泡实现,若原数组本身就是有序的(这是最好情况),仅需n-1次比较就可完成;若是倒序,比较次数为 n-1+n-2+...+1=n(n-1)/2,交换次数和比较次数等值。所以,其时间复杂度依然为O(n2)。综合来看,冒泡排序性能还还是稍差于上面那种选择排序的。

直接插入排序

直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。

/**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

简单插入排序在最好情况下,需要比较n-1次,无需交换元素,时间复杂度为O(n);在最坏情况下,时间复杂度依然为O(n2)。但是在数组元素随机排列的情况下,插入排序还是要优于上面两种排序的。

本文列举了排序算法中最基本的三种算法(简单选择,冒泡,插入),这三种排序算法的时间复杂度均为O(n2),后续会陆续更新其他更高阶一些的排序算法,时间复杂度也会逐步突破O(n2)

© 著作权归作者所有

共有 人打赏支持
写代码的奥特曼
粉丝 11
博文 86
码字总数 109060
作品 0
杭州
高级程序员
私信 提问
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
06/05
0
0
史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程; 外部排序:指的是排序...

马哥教育
2017/10/25
0
0
面试 10:玩转 Java 选择排序和插入排序

面试 10:Java 玩转选择排序和插入排序 昨天给大家讲解了 Java 玩转冒泡排序,大家一定觉得并没有什么难度吧,不知道大佬们玩转了吗?不知道大家有没有多加思考,实际上在我们最后的一种思路...

nanchen2251
07/17
0
0
面试 10:玩转 Java 选择和插入排序,附冒泡最终源码

昨天给大家讲解了 Java 玩转冒泡排序,大家一定觉得并没有什么难度吧,不知道大佬们玩转了吗?不知道大家有没有多加思考,实际上在我们最后的一种思路上,还可以再继续改进。 我们先看看昨天...

南尘
07/17
0
0
面试 10:玩转 Java 选择和插入排序,附冒泡最终版本

面试 10:Java 玩转选择排序和插入排序 昨天给大家讲解了 Java 玩转冒泡排序,大家一定觉得并没有什么难度吧,不知道大佬们玩转了吗?不知道大家有没有多加思考,实际上在我们最后的一种思路...

nanchen2251
07/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nuc970 uboot nand-boot,kernel, filesystem 烧录位置

一 烧写到Nand Flash **1.1 **相关文件说明 l BSP版本:nuc970bsp-release-20150519.zip l NuWriter版本:2015/04/28-V01,nuvoTon Nu-Writer V1.0 l 烧写文件: u-boot-spl.bin:负责将u-b......

CookieDemo
51分钟前
1
0
python中sort和sorted函数小结

L.sort(cmp=None, key=None, reverse=False) sorted(iterable, cmp=None, key=None, reverse=False) 这样看,sorted函数只比sort函数多一个iterable参数,其余没什么不同,iterable是一个迭代......

上官夏洛特
今天
3
0
thinkphp 常用SQL执行语句总结

第一条:Db::tablera('vr_panomas')->where(['delete_time'=>0,'id'=>['in',$pids]])->field(['id'=>'id','post_thumb'=>'thumb','post_title'=>'title','post_tags'=>'tags','post_price'=>......

koothon
今天
5
0
支付宝返回状态resultStatus意思

上一篇集成支付宝的时候,会有一些支付宝返回的resultStatus,具体意思是: 9000 订单支付成功 8000 正在处理中 4000 订单支付失败 6001 用户中途取消 6002 网络连接出错 还有memo,意思就是...

RainOrz
今天
3
0
electron webview 页面加载事件顺序

1.did-start-loading 页面开始加载 2.load-commit 主页面文档加载 3.page-title-updated title 4.dom-ready 主页面 dom 加载完成 5.load-commit frame文档加载 6.did-frame-finish-load fram......

dubox
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部