面试准备之常见排序算法的总结！

ゞ浴缸里的玫瑰 2022-08-26 00:57 206阅读 0赞

# 1.插入排序 #

## 1.1直接插入排序 ##

这是一种最简单，最容易理解的排序方式，其排序思路如下：假设待排序数组为R\[0,1,2,i...n-1\]，首先将R\[0\]看作一个有序的子序列（尽管它只有一个数），从R\[1\]至R\[n-1\]开始，逐一向该子序列进行插入操作（由小到大排序），那么左半部分的有序子序列将不断增加，而右半部分的待排序列将不断减少，当有序子序列的长度等于原序列时， 排序结束。  
   时间复杂度：O(n^2)  
   稳定性：稳定

然而，如何找到待插入元素的位置是插入排序的关键，直接插入排序用的就是最“暴力”的逐一查找法：

暴力算法1：将R\[i\]与有序子序列所有的元素比较（不移动，只寻找），找到待插入的位置j后，将R\[j，i-1\]一次性移动到R\[j+1，i\]，腾出R\[j\]的位置让R\[i\]来插入，其中遍历了一次，移动了一次，很是暴力。

暴力算法2：在算法1的基础上，每次寻找时，若R\[i\]小于子序列的元素，就与其交换，这样在遍历的同时就完成了移动的动作，优于算法1。

算法1的实现如下，

//算法1
    		public void insertSort1(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=1;i<=len-1;i++){//从第二个数开始插入
    				int location=i;//寻找待插入位置
    				int tmp=r[i].value;//暂存待插入元素
    				for(int j=i-1;j>=0;j--){
    					//j代表有序子序列的最大索引
    					if(!this.compare(r[i],r[j])){
    						//若小于，则继续寻找位置
    						location=j;
    					}
    				}
    				
    				if(location!=i){
    				//将R[location...i-1]移动到R[location+1,i],腾出location处的位置
    					for(int k=i;k>location;k--){
    						r[k].value=r[k-1].value;
    					}
    				}
    				r[location].value=tmp;//填充待插入元素
    			}
    			//输出
    			this.print(r);
    		}

算法2的实现如下：

//算法2，优于算法1
    		public void insertSort2(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=1;i<=len-1;i++){//从第二个数开始插入
    				int tmp=r[i].value;//暂存待排序元素
    				int j=i-1;
    				while((j>=0)&&(tmp<r[j].value)){
    					
    					r[j+1].value=r[j].value;
    					j--;
    					
    				}
    				r[j+1].value=tmp;//填充待插入元素
    			}
    			//输出
    			this.print(r);
    		}

而直接插入排序一般用算法2就行了。

## 1.2折半插入排序 ##

尽管直接插入排序的算法2优于算法1，但它们都比较暴力，因为若子序列的长度为n，则复杂度就为O(n)。假若有一个数我们第一眼就知道它应该插入到最前面，而有序序列又很长，那么这就是最坏的情况（得从后面一个一个找）。为了能快速找到待插入位置，就引入了能快速寻找的折半查找。

折半插入排序的原理就是：   在直接插入排序排序的基础上，每次寻找插入位置时将有序子序列分解为高半区high， 和低半区low，mid为(low+high)/2,当待排元素key小于（大于）mid时，则它应该插入低半区（高半区），依次循环。

时间复杂度：O(n^2)  
   稳定性：稳定

算法实现：

public void halfInsert(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			int low,high,tmp;
    			int mid;
    			for(int i=0;i<len;i++){
    				low=0;//low指向子序列的起始位置
    				high=i-1;//high指向末端		
    				tmp=r[i].value;//待插入元素
    				//寻找位置
    				while(low<=high){
    					mid=(low+high)/2;
    					if(r[i].value<r[mid].value)//小于mid
    						high=mid-1;
    					else
    						low=mid+1;
    				}
    				//high+1则为待插入位置
    				//将r[high+1...i-1]移动到r[high+2...i],腾出high+1的位置
    				for(int j=i;j>high+1;j--){
    					r[j].value=r[j-1].value;
    				}
    				r[high+1].value=tmp;
    			}
    			//输出
    			this.print(r);
    		}

##    1.3希尔排序 ##

希尔排序是一种分组插入的排序方式，它首先将待排序R\[\]序列按照d1=R.length/2的增量进行分组，然后组内的元素进行插入排序，然后以d2=d1/2的增量重复上述操作，直至dn=1（即所有元素都在同一组内）则完成排序。  
   时间复杂度：O(logn\*logn\*n)=O(n\*log2n)  
   稳定性：不稳定

算法实现：

public void shellSort(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			int d=len/2;
    			while(d>=1){
    				//以d为分组的序列进行直接插入排序，
    				for(int i=d;i<len;i=i+d){
    					int tmp=r[i].value;//暂存待排序元素
    					int j=i-d;//有序子序列的最大索引
    					while(j>=0&&tmp<r[j].value){
    							r[j+d].value=r[j].value;
    							j=j-d;
    					}
    					//此时的j+d为待插入位置
    					r[j+d].value=tmp;
    				}
    				d=d/2;//增量递减
    			}
    			//输出
    			this.print(r);
    		}

# 2.交换排序 #

## 2.1冒泡排序 ##

冒泡排序是从第一个元素起，比较相邻的两个元素，按由小到大排序，若前一个大于后一个元素，则交换彼此。如此重复n-1趟，每趟都会将该趟最大的元素放置趟尾，好像“冒泡”一样。  
   时间复杂度：O(n^2)  
   稳定性：稳定

算法实现：

public void bubbleSort(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=0;i<len;i++){//len-1趟
    				for(int j=0;j<len-i-1;j++){//每趟交换的次数
    					if(r[j].value>r[j+1].value){
    						this.swap(r[j],r[j+1]);
    					}
    				}		
    			}
    			//输出
    			this.print(r);
    		}

##    2.2快速排序 ##

快速排序是在冒泡排序的基础上改进的：首先选取R\[0...n\]序列中的R\[0\]做为关键字，low和high分别指向序列的开始和结束（低半区和高半区），将小于（大于）R\[0\]的元素从低半区（高半区）交换至高半区（低半区）而中间则插入R\[0\]，递归对两边子序列也进行上述操作，直至子序列元素的个数为1。  
   时间复杂度：将原始序列无限按二分法分解则复杂度为logn,遍历时low--->high则为n，所以O(logn\*n)=O(nlogn)  
   稳定性：不稳定

算法实现：

public void quickSort(TestSort[] src,int lowIndex,int highIndex){
    			
    				if(lowIndex<highIndex){//保证递归时至少有2个元素
    					TestSort[] r=src;
    					int low=lowIndex;
    					int high=highIndex;
    				  int location;
    					int key=r[low].value;//关键字
    						while(low<high){
    							while(low<high&&r[high].value>=key){	
    								high--;
    							}
    							if(low<high){
    								this.swap(r[high],r[low]);
    							}
    							while(low<high&&r[low].value<=key){		
    								low++;
    							}
    							if(low<high){
    								this.swap(r[low],r[high]);
    							}
    						}		
    					//待插入位置location=low=high
    					location=low;
    					r[location].value=key;
    					quickSort(r,lowIndex,location-1);//低区递归
    					quickSort(r,location+1,highIndex);//高区递归		
    				}
    				
    		}

#    3.选择排序 #

## 3.1简单选择排序 ##

设待排序列R\[0...i...n-1\],待排元素为R\[i\],有序子序列为R\[0...i-1\],无序子序列为R\[i...n-1\],则在 R\[i...n-1\]中寻找最小的元素，并与R\[i\]交换(相当于补在有序子序列的后边)，直到有序子序列的长度等于原长为止。  
   时间复杂度：O(n^2)  
   稳定性：不稳定

算法实现：

public void simpleChoose(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=0;i<len;i++){
    				int location=i;
    				int min=r[location].value;
    				for(int j=i+1;j<len;j++){
    					if(r[j].value<min){
    						location=j;
    						min=r[j].value;
    					
    					}
    				}
    				if(location!=i){
    					//找到了，在location处
    					this.swap(r[location],r[i]);
    				}
    				
    			}
    			//输出
    			this.print(r);
    		}

所有排序算法实现：

import java.util.ArrayList;
    public class TestSort{
    		public static final int SYSMBOL=0XFF;//占位符号
    		public int value;//值
    		public int index;//索引
    
    		/*
    			原本想利用对象最为带排序元素存些其他信息，最后发现木有必要。。
    		*/
    		public TestSort(int value,int index){
    			
    			this.value=value;
    			this.index=index;
    		}
    		public TestSort(){}
    		
    		//交换
    		public void swap(TestSort a,TestSort b){
    			
    			TestSort tmp=new TestSort();
    			tmp.value=a.value;
    			//tmp.index=a.index;
    			
    			a.value=b.value;
    			//a.index=b.index;
    			
    			b.value=tmp.value;
    			//b.index=tmp.index;
    			
    		
    		}
    		
    		//比大小
    		public Boolean compare(TestSort a,TestSort b){
    			if(a.value>b.value)
    				return true;
    				return false;
    		}
    		
    		//输出
    		public void print(TestSort[] r){
    		
    			System.out.printf("%s","索引：");
    			for(TestSort e : r){
    				
    				if(e.value!=TestSort.SYSMBOL){
    					System.out.printf("%s ",e.index<10?"0"+e.index:e.index);
    				}
    			}
    			System.out.println("\n");
    			System.out.printf("%s","数组：");
    			for(TestSort e : r){
    				if(e.value!=TestSort.SYSMBOL){
    					System.out.printf("%s ",e.value<10?"0"+e.value:e.value);
    				}
    			}
    			System.out.println("\n");
    		}
    		
    		//复制元素，由于数组为引用类型
    		public TestSort[] copy(TestSort[] src){
    			  ArrayList<TestSort> list=new ArrayList<TestSort>();
    				for (TestSort e : src) {
    				 	list.add(new TestSort(e.value,e.index));
    				}
    				TestSort[] r=new TestSort[list.size()];
    				return list.toArray(r);
    		}
    		/********************************1.插入排序***************************************************/
    		/*
    		---------------------------------1.1直接插入排序：---------------------------------------------------
    			这是一种最简单，最容易理解的排序方式，其排序思路如下，
    		假设待排序数组为R[0,1,2,i...n]，首先将R[0]看作一个有序的
    		子序列（尽管它只有一个数），从R[1]至R[n]开始，逐一向该子序列
    		进行插入操作（由小到大），那么左半部分的子序列将不断增加，而
    		有半部分的待排序列将不断减少，当有序子序列的长度等于原序列时，
    		排序结束。
    			时间复杂度：O(n^2)
    			稳定性：稳定
    		*/
    		
    		//算法1
    		public void insertSort1(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=1;i<=len-1;i++){//从第二个数开始插入
    				int location=i;//寻找待插入位置
    				int tmp=r[i].value;//暂存待插入元素
    				for(int j=i-1;j>=0;j--){
    					//j代表有序子序列的最大索引
    					if(!this.compare(r[i],r[j])){
    						//若小于，则继续寻找位置
    						location=j;
    					}
    				}
    				
    				if(location!=i){
    				//将R[location...i-1]移动到R[location+1,i],腾出location处的位置
    					for(int k=i;k>location;k--){
    						r[k].value=r[k-1].value;
    					}
    				}
    				r[location].value=tmp;//填充待插入元素
    			}
    			//输出
    			this.print(r);
    		}
    		
    		
    		//算法2，优于算法1
    		public void insertSort2(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=1;i<=len-1;i++){//从第二个数开始插入
    				int tmp=r[i].value;//暂存待排序元素
    				int j=i-1;
    				while((j>=0)&&(tmp<r[j].value)){
    					
    					r[j+1].value=r[j].value;
    					j--;
    					
    				}
    				r[j+1].value=tmp;//填充待插入元素
    			}
    			//输出
    			this.print(r);
    		}
    		
    		
    		/*
    		---------------------------------1.2折半插入排序：---------------------------------------------------
    					在简单插入排序中，为了插入到有序子序列中的合适位置，每次不得不遍历所有的子序列，这样其实复杂度很大。
    			假若有一个数我们第一眼就知道它应该插入到最前面，而有序序列又很长，那么这就是最坏的情况（得从后面一个一个找）。
    			为了快速找到合适的插入位置，可以利用折半查找：在简单排序的基础上，每次寻找插入位置时将有序子序列分解为高半区high，
    			和低半区low，mid为(low+high)/2,当待排元素key小于（大于）mid时，则它应该插入低半区（高半区），依次循环，这样复杂度
    			一下子就降为logn了，于是，折半插入排序的性能为，
    			时间复杂度：O(nlogn)
    			稳定性：稳定
    		*/
    		public void halfInsert(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			int low,high,tmp;
    			int mid;
    			for(int i=0;i<len;i++){
    				low=0;//low指向子序列的起始位置
    				high=i-1;//high指向末端		
    				tmp=r[i].value;//待插入元素
    				//寻找位置
    				while(low<=high){
    					mid=(low+high)/2;
    					if(r[i].value<r[mid].value)//小于mid
    						high=mid-1;
    					else
    						low=mid+1;
    				}
    				//high+1则为待插入位置
    				//将r[high+1...i-1]移动到r[high+2...i],腾出high+1的位置
    				for(int j=i;j>high+1;j--){
    					r[j].value=r[j-1].value;
    				}
    				r[high+1].value=tmp;
    			}
    			//输出
    			this.print(r);
    		}
    		
    		/*
    		---------------------------------1.3希尔排序：---------------------------------------------------
    					希尔排序是一种分组插入的排序方式，它首先将待排序R[]序列按照d1=R.length/2的增量进行分组，然后
    			组内的元素进行插入排序，然后以d2=d1/2的增量重复上述操作，直至dn=1（即所有元素都在同一组内）则
    			完成排序。
    			时间复杂度：O(logn*logn*n)=O(n*log2n)
    			稳定性：不稳定
    		*/
    		public void shellSort(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			int d=len/2;
    			while(d>=1){
    				//以d为分组的序列进行直接插入排序，
    				for(int i=d;i<len;i=i+d){
    					int tmp=r[i].value;//暂存待排序元素
    					int j=i-d;//有序子序列的最大索引
    					while(j>=0&&tmp<r[j].value){
    							r[j+d].value=r[j].value;
    							j=j-d;
    					}
    					//此时的j+d为待插入位置
    					r[j+d].value=tmp;
    				}
    				d=d/2;//增量递减
    			}
    			//输出
    			this.print(r);
    		}
    		/********************************2.交换排序***************************************************/
    		/*
    		---------------------------------2.1冒泡排序：---------------------------------------------------
    					冒泡排序是从第一元素起，比较相邻的两个元素，按由小到大排序，若前一个大于后一个元素，则交换彼此。
    			如此重复n-1趟，每趟都会将该趟最大的元素放置趟尾，好像“冒泡”一样。
    			时间复杂度：O(n^2)
    			稳定性：稳定
    		*/
    		public void bubbleSort(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=0;i<len;i++){//len-1趟
    				for(int j=0;j<len-i-1;j++){//每趟交换的次数
    					if(r[j].value>r[j+1].value){
    						this.swap(r[j],r[j+1]);
    					}
    				}		
    			}
    			//输出
    			this.print(r);
    		}
    		
    		/*
    		---------------------------------2.2快速排序：---------------------------------------------------
    					快速排序是在冒泡排序的基础上改进的：首先选取R[0...n]序列中的R[0]做为关键字，low和high分别指向
    			序列的开始和结束（低半区和高半区），将小于（大于）R[0]的元素从低半区（高半区）交换至高半区（低半区）
    			而中间则插入R[0]，递归对两边子序列也进行上述操作，直至子序列的个数为1
    			时间复杂度：将原始序列无限按二分法分解则复杂度为logn,遍历时low--->high则为n
    									所以O(logn*n)=O(nlogn)
    			稳定性：不稳定
    		*/
    		public void quickSort(TestSort[] src,int lowIndex,int highIndex){
    			
    				if(lowIndex<highIndex){//保证递归时至少有2个元素
    					TestSort[] r=src;
    					int low=lowIndex;
    					int high=highIndex;
    				  int location;
    					int key=r[low].value;//关键字
    						while(low<high){
    							while(low<high&&r[high].value>=key){	
    								high--;
    							}
    							if(low<high){
    								this.swap(r[high],r[low]);
    							}
    							while(low<high&&r[low].value<=key){		
    								low++;
    							}
    							if(low<high){
    								this.swap(r[low],r[high]);
    							}
    						}		
    					//待插入位置location=low=high
    					location=low;
    					r[location].value=key;
    					quickSort(r,lowIndex,location-1);//低区递归
    					quickSort(r,location+1,highIndex);//高区递归		
    				}
    				
    		}
    		
    		/********************************3.选择排序***************************************************/
    		/*
    		---------------------------------3.1简单选择排序：---------------------------------------------------
    					设待排序列R[0...i...n-1],待排元素为R[i],有序子序列为R[0...i-1],无序子序列为R[i...n-1],则在
    			R[i...n-1]中寻找最小的元素，并与R[i]交换(相当于补在有序子序列的后边)，直到有序子序列的长度等于原长为止。
    			时间复杂度：O(n^2)
    			稳定性：不稳定
    		*/
    		public void simpleChoose(TestSort[] src){
    			TestSort[] r=this.copy(src);
    			int len=r.length;
    			for(int i=0;i<len;i++){
    				int location=i;
    				int min=r[location].value;
    				for(int j=i+1;j<len;j++){
    					if(r[j].value<min){
    						location=j;
    						min=r[j].value;
    					
    					}
    				}
    				if(location!=i){
    					//找到了，在location处
    					this.swap(r[location],r[i]);
    				}
    				
    			}
    			//输出
    			this.print(r);
    		}
    		
    		public static void main(String[] args){
    			TestSort obj=new TestSort();
    			TestSort[] r=new TestSort[]{
    				new TestSort(10,0),
    				new TestSort(1,1),
    				new TestSort(9,2),
    				new TestSort(2,3),
    				new TestSort(8,4),
    				new TestSort(3,5),
    				new TestSort(7,6),
    				};
    				System.out.println("原始数组：");
    				obj.print(r);
    				
    				System.out.println("直接插入算法1：");
    				obj.insertSort1(r);
    				
    				System.out.println("直接插入算法2：");
    				obj.insertSort2(r);
    				
    				System.out.println("折半插入算法：");
    				obj.halfInsert(r);
    				
    				System.out.println("希尔排序算法：");
    				obj.shellSort(r);
    				
    				System.out.println("冒泡算法：");
    				obj.bubbleSort(r);
    				
    				System.out.println("快速排序：");
    				obj.quickSort(r,0,r.length-1);
    				obj.print(r);
    				
    				System.out.println("简单选择数组：");
    				obj.simpleChoose(r);
    			  
    				
    				
    		}
    	}

结果：

![Center][]

[Center]: /images/20220824/bc82fe04a7f7499f9faeb7ec16107925.png