选择排序、插入排序、希尔排序总结

╰+哭是因爲堅強的太久メ 2022-09-28 11:57 155阅读 0赞

本来昨天想写最小生成树的kruskal算法，但是其中需要将图的边集数组进行排序，要用到排序算法，所以暂时先将kruskal算法放一下，把排序算法好好复习和总结一遍

以下的排序结果默认为非递减

## 1、选择排序 ##

选择排序的思想：从第i个元素开始（i=1,i++），遍历一遍数组，找出数组中的最小值，然后与第i个元素交换位置，i++,不断的循环下去直到i>数组长度（长度为length-1,第0个元素习惯用作哨兵位）

看看具体算法

public void selectSort(int arc[]){
    		
    		int min;
    		for(int j=1;j<arc.length;j++){
    			min = j;
    			for(int i=j+1;i<arc.length;i++){
    				if(arc[i]<arc[min])
    					min = i;				
    			}
    			each(arc,j,min);  //交换arc[j]和arc[min]的位置
    			System.out.println(arc[j]); 
    		}
    		
    	}

选择排序的几个特点：

1.时间复杂度为**O（n^2）**；

**2.运行的时间与输入参数的初始状态无关**，因为每一次的遍历都不会为下一次提供任何有用的信息；

**3.数据的移动是最少的。**

## 2、插入排序 ##

插入排序的思想：将第i个元素与i-1的元素比较，如果第i个元素较小，则把其插入到arc\[0\]的哨兵位，然后比哨兵位大的元素不断的往后移动一位，最后将哨兵位的元素插入到最后移动的那个位置。注：i一般从2开始，因为假设第1位已经排好序了。

看看具体算法

public void insertSort(int arc[]){
    		int i;
    		for(int j=2;j<arc.length;j++){
    			if(arc[j]<arc[j-1]){
    				arc[0] = arc[j];	 //插入哨兵位
    				for(i=j-1;arc[i]>arc[0];i--){
    					arc[i+1] = arc[i];      //元素不断向后移动一位
    				}
    				arc[i+1] = arc[0];	//将哨兵位的元素插入到最后一次移动的位置			
    			}
    		}
    		output(arc);             //输出排好序的数组元素
    	}

output(int arc\[\])具体代码

private void output(int[] arc) {
    		for(int i=1;i<arc.length;i++){
    			System.out.println(arc[i]);
    		}
    		
    	}

插入排序的几个特点：

1.时间复杂度为**O（n^2）**，但插入排序平均速度要比选择排序快；

2.**运行时间与输入的参数初始化状态有关**，比如对于部分有序的数组十分高效；

## 3、希尔排序 ##

希尔排序思想：希尔排序是简单的改进了插入排序，交换不相邻的元素以进行局部的排序，并最终用插入排序对局部的数组排序。

看看具体代码

public void shellSort(int arc[]){
    		int i;
    		int increment = arc.length/3+1;   //增量序列
    		while(increment>0){
    			for(int j=1+increment;j<arc.length;j++){
    				if(arc[j]<arc[j-increment]){
    					arc[0] = arc[j];
    					for(i=j-increment;i>0&&arc[i]>arc[0];i-=increment){//i>0是表示当要插到第1位时的条件，且i>0一定要在逻辑运算中的前面
    						arc[i+increment] = arc[i];              //否则会ArrayIndexOutOfBoundsException
    					}
    					arc[i+increment] = arc[0];
    				}
    			}
    			increment/=3;
    		}	
    		output(arc);             //输出排好序的数组元素		
    	}

希尔排序的几个特点：

1.时间复杂度为**O（n^3/2）**

2.**对于较大的数组，希尔排序的速度相较于插入排序的优势更加明显**

## **总结** ##

虽然选择排序和插入排序的时间复杂度一样，但是选择排序的运行时间和参数的初始状态无关，只要数组参数的长度一样，不管数组里面的元素初始排序是怎样的，运行时间都不会有改变（默认理想环境，忽略硬件环境造成的误差）。而插入排序的运行时间和参数初始状态有关，特别是对于部分有序数组，十分高效，因此插入排序比选择排序的平均运行时间要快一些。

希尔排序是对插入排序的改进，对距离increment的元素进行比较和交换，元素的跳跃跨度较大，使得希尔排序在较大的数组中的运行时间要比插入排序短。