微信号:grzlwx

介绍:光荣之路官方资讯

八大种必知排序算法(二) 选择排序,插入排序,希尔算法

2015-08-31 21:49 光荣之路

一、选择排序

  1、基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

  

  2、实例

  3、算法实现

/**
* 选择排序算法
* 在未排序序列中找到最小元素,存放到排序序列的起始位置
* 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。
* 以此类推,直到所有元素均排序完毕。
* @param numbers
*/
public static void selectSort(int[] numbers)
{
int size = numbers.length; //数组长度
int temp = 0 ; //中间变量

for(int i = 0 ; i < size ; i++)
{
int k = i; //待确定的位置
//选择出应该在第i个位置的数
for(int j = size -1 ; j > i ; j--)
{
if(numbers[j] < numbers[k])
{
k = j;
}
}
//交换两个数
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}


二、插入排序

  1、基本思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。

  2、实例

  

  3、算法实现

/**
* 插入排序
*
* 从第一个元素开始,该元素可以认为已经被排序
* 取出下一个元素,在已经排序的元素序列中从后向前扫描
* 如果该元素(已排序)大于新元素,将该元素移到下一位置
* 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到该位置中
* 重复步骤2
* @param numbers 待排序数组
*/
public static void insertSort(int[] numbers)
{
int size = numbers.length;
int temp = 0 ;
int j = 0;

for(int i = 0 ; i < size ; i++)
{
temp = numbers[i];
//假如temp比前面的值小,则将前面的值后移
for(j = i ; j > 0 && temp < numbers[j-1] ; j --)
{
numbers[j] = numbers[j-1];
}
numbers[j] = temp;
}
}

4、效率:

时间复杂度:O(n^2).

(作者:WhyWin 来源:http://www.cnblogs.com/0201zcr/p/4764427.html)


 
            
 
            
 
            
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           

一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!

光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499



 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 cocos2dx(三) hello world 这么神的生活技能,你真的一个都不会? 程序员常去的14个顶级开发社区 学习的节奏 Python+tkinter+pillow实现屏幕任意区域截图