选择排序,插入排序

Bertha 。 2021-11-09 00:42 269阅读 0赞

## 排序 ##

*  整体围绕解决如下一个混乱整数数组排序的问题
 *  排序结果为升序
 *  未排序整数数组a\[\]

## 选择排序 ##

### 原理 ###

*  每次将未排序部分最小的数字和其第一个位置的数字交换,并其第一个位置的数字转化为已排序部分,如此循环直至已排序部分包含数组全部数字
 *  已排序的部分作高亮处理
 *  一开始都是未排序的部分

*  将未排序部分最小的数字(0)和其第一个位置的数字(2)交换,并其第一个位置的数字转化为已排序部分

*  将未排序部分最小的数字(1)和其第一个位置的数字(3)交换,并其第一个位置的数字转化为已排序部分

*  将未排序部分最小的数字(2)和其第一个位置的数字(3)交换,并其第一个位置的数字转化为已排序部分

*  将未排序部分最小的数字(3)和其第一个位置的数字(5)交换,并其第一个位置的数字转化为已排序部分

*  将未排序部分最小的数字(4)和其第一个位置的数字(4)交换,并其第一个位置的数字转化为已排序部分

*  将未排序部分最小的数字(5)和其第一个位置的数字(5)交换,并其第一个位置的数字转化为已排序部分

### Code by java ###

public class Sort { static public void selectSort(int[] a){//传入一个数组 for(int i=0;i<a.length;i++){ int min=i,temp;//min是未排序部分最小值的下标,初始是a[i] for(int j=i+1;j<a.length;j++)//从未排序部分开始找最小值的下标 if(a[j]<a[min]) min=j; temp=a[i];//将未排序部分中最小值放到未排序部分的第一个位置,转换为排序部分 a[i]=a[min]; a[min]=temp; } } }

--------------------

## 插入排序 ##

### 原理 ###

*  每次将未排序部分第一个数字归入排序部分,由于已排序部分有序,依次从最高位置到最低位置比较,直到找到合适的位置
 *  已排序的部分作高亮处理
 *  一开始都是未排序的部分

*  未排序部分第一个数字并入排序部分.最开始这一步通常不用操作

*  未排序部分第一个数字(3)并入排序部分.

*  未排序部分第一个数字(1)并入排序部分.

*  未排序部分第一个数字(5)并入排序部分.

*  未排序部分第一个数字(5)并入排序部分.

*  未排序部分第一个数字(5)并入排序部分.

### Code by java ###

public class Sort { static public void insertSort(int[] a){ for(int i=1;i<a.length;i++){//由于未排序第一个数字不用插入,所以直接从下标为1的位置开始 int temp=a[i];//拷贝未排序部分的第一个数字 int j;//记录最后未排序部分第一个数字的落点 for(j=i-1;j>-1;j--){//由于插入第i个,那么已排序部分最高位下标就是i-1,从大到小比较 if(a[j]>temp)//如果这个数比未排序部分第一个数字大,那么这个数字后移一位,第一个数字已经拷贝,所以不用担心覆盖(这是一种优化) a[j+1]=a[j];//后移 else break;//不然位置合适就跳出循环 } a[j+1]=temp;//将未排序部分第一个数字放到合适的位置 } } }

--------------------

## 希尔排序(shell sort) ##

### 原理 ###

*  先将整个待排记录序列分割为若干个子序列分别进行直接插入排序,待整个序列'基本有序'时,再对全体记录进行一次直接插入排序
 *  子序列的构成并不是简单的逐段分割,而是将相隔某个增量的记录组成一个子序列.增量的选择很重要.
 *  希尔排序和插入排序的不同是,在增量大于1时,子序列间的排序具有跳跃性,在最后的一次插入排序,由于整个序列已经'基本有序',此时的插入排序更为快速,这就是希尔排序优于插入排序的原因

### 示例 ###

*  以下示例增量为1,3,5
 *  插入第一个数字无需调整,仔细观察每趟排序,从第增量个数字开始,每个数字都需要插入操作,当然是在同一增量序列中
 *  优先进行增量大的序列

![希尔排序][1656494-20190801144810808-971185714.jpg]

### Code by java ###

*  这里取增量为1,4,13...(3\*n+1)

static public void shellSort(int[] a){ int h=1; while (h<a.length/3) h=h*3+1;//求出最大增量 while (h>0){//增量大于零 for(int i=h;i<a.length;i+=h){//每次将以增量为下标位置开始的数字往前插入到数组中,插入必须在同一增量序列中 int temp=a[i]; int j; for(j=i-h;j>-1;j-=h){ if(a[j]>temp) a[j+h]=a[j]; else break; } a[j+h]=temp; } h/=3;//增量改变为较小的增量 } }

转载于:https://www.cnblogs.com/redo19990701/p/11282494.html

[1656494-20190801144810808-971185714.jpg]: /images/20211108/7c2a276b3d9f4522afd5fa3b0f591c99.png