几种基本的排序算法

约定不等于承诺〃 2022-09-25 00:25 173阅读 0赞

1.冒泡排序:

冒泡排序的目标就是通过第一次循环将最大(最小)的数找出来,第二次循环将次大(次小)的数找出来....................,

冒泡排序在最坏情况下的时间复杂度为O(n^2),平均时间复杂度:O(n^2),最好情况下的时间复杂度是:O(n),算法稳定。

图解:

![08015657_WTZ5.gif][]

代码:

//冒泡排序
    public class BunnleSort {
    	public static void sort(int[] source){
    		for(int i=source.length-1;i>0;i--){
    			for(int j=0;j<i;j++){
    				if(source[j]>source[j+1]){
    					int temp=source[j+1];
    					source[j+1]=source[j];
    					source[j]=temp;
    					
    				}
    			}
    		}
    	}
    	public static void main(String[] args) {
    		int[] a={4,3,8,9,100,11,456,87,54,-1,0};
    		sort(a);
    		for(int ok:a){
    			System.out.printf("%d ",ok);
    		}
    	}
    
    }

2.选择排序:

选择排序的目标是在一堆未排序的数中选出最小的元素存放在第一个位置,然后再从剩余的未排序的数中选出第二小的数,然后存放在第二个位置....,直到所有的元素都排序完毕。

选择排序算法的时间复杂度都是:O(n^2),算法稳定。

图解:

(待添加)

代码:

//选择排序
    public class SelectSort {
    	public static void selectSort(int[] source){
    		for(int i=0;i<source.length;i++){
    			for(int j=i+1;j<source.length;j++){
    				if(source[i]>source[j]){
    					int temp=source[j];
    					source[j]=source[i];
    					source[i]=temp;
    				}
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] a={1,9,2,5,87,34,46,89,40,32,29};
    		selectSort(a);
    　　　　　　　　　for(int ok:a){
    	　　　　　　System.out.printf("%d ",ok);
    		}

\}\}

3.插入排序

插入排序的目的就是先把位置1到位置2的排好序,然后再将位置1~3的数排好序......然后再把所有的数都排好序。

(1),(1,2),(1,2,3)......(1,2,3....,k)

图解:

(待添加)

具体的步骤如下:

1.从第一个元素开始,该元素认为是已近排序好的

2.取下一个元素,在已经排序的序列中从后往前扫描

3.如果已排序组中的元素大于新元素,那么将该元素移动到下一个位置

4.重复步骤3,如果在已排序的组中找到比新元素更小的数,那么算法停止

5.将新元素插入到该位置上

6.重复步骤2

插入排序在最坏情况下的时间复杂度为O(n^2),最好情况下的时间复杂度是:O(n),算法稳定。

//插入排序
    public class InsertSort {
    	public static void insertSort(int[] source){
    		for(int i=1;i<source.length;i++){
    			for(int j=i;(j>0)&&(source[j]<source[j-1]);j--){
    				int temp=source[j-1];
    				source[j-1]=source[j];
    				source[j]=temp;
    			}
    		}
    	}
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] a={4,2,1,6,7,19,35,56,78,98,89,0,-100};
    		insertSort(a);
    		for(int ok:a){
    			System.out.println(ok);
    		}
    	}
    
    }

4.二分排序:

基本思想:

二分排序和前面讲的直接插入排序比较类似,假设前面的序列已经排列完毕,然后在未排序的数组中选取第一个数,利用二分法在已排序的数中找到比需要插入的数大的那个数,然后将未排序序列中第一个数,也就是程序中的temp,插入刚刚利用二分法找到的那个数的位置上，相对于直接插入排序通过一个一个比较,然后再插入效率高了很多。

二分排序在最坏情况下的时间复杂度是O(n^2/2),最好情况下的时间复杂度是O(n),算法稳定。

public class HalfSplitSort {
    	private static void sort(int[] a) {
    		        for (int i = 0; i < a.length; i++) {
    		             int temp = a[i];
    		             int left = 0;
    		             int right = i-1;
    		             int mid = 0;
    		             while(left<=right){  //求left
    		                 mid = (left+right)/2;
    		                 if(temp<a[mid]){
    		                     right = mid-1;
    		                 }else{
    		                     left = mid+1;
    		                 }
    		             }
    		             for (int j = i-1; j >= left; j--) {
    		                 a[j+1] = a[j];
    		             }
    		             if(left != i){
    		                 a[left] = temp;
    		             }
    		         }
    		     }
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] a={8,2,1,5,3,6,0,-5,1,1};
    		sort(a);
    		for(int ok:a){
    			System.out.printf("%d ",ok);
    		}
    	}
    		
    
    }

5.堆排序

在进行堆排序之前,我们首先要了解一个概念,堆分为大顶堆和小顶堆,key\[i\]>=key\[2i+1\]&&key\[i\]>key\[2i+2\]称为大顶堆,key\[i\]<=key\[2i+1\]&&key\[i\]>key\[2i+2\]的称为小顶堆,了解了以上的知识之后,我们开始堆排序的讲解。

1.首先,假设排序的数一共有n个，我们把所有的数据构造成一个大顶堆(这样我们得到了这组数中的最大值)

2.将堆顶和最后一个元素互换(最大的一个元素就被排在了最后的位置上)

3.然后将剩下的n-1个数构造成一个大顶堆(找到了次大的数)

4.将此刻堆顶的值和倒数第二个叶子节点进行互换

5.重复上述的步骤,知道所有的元素排序完毕!

//因为二叉树的根节点经过buildMaxHeap后必定是最大值
    //然后交换一下下面的节点和根节点就可以把所有的元素从小到大排序
    public class HeapSort {
    
    	public static void main(String[] args) {
    		-+
    		int[] a={38,46,56,40,84,79};
    		
    		for(int i=0;i<a.length-1;i++){
    			buildMaxHeap(a,a.length-1-i);
    			swap(a,0,a.length-1-i);//交换堆顶和最后一个元素
    			
    		}
    		for(int ok:a){
    		System.out.printf("%d ",ok);
    		}
    		
    		
    	}
    	public static void buildMaxHeap(int[] data,int lastIndex){//建堆
    		//从最下面的额父节点开始
    		for(int i=(lastIndex-1)/2;i>=0;i--){
    			//t保存正在判断的节点
    			int t=i;//这个节点左边的子树是2t,右边的子数是2t+1
    			while(2*t+1<=lastIndex){//如果当前的子节点存在
    				int bIndex=2*t+1;
    				if((bIndex)<lastIndex){//如果右结点存在
    					if(data[bIndex]<data[bIndex+1]){//左结点小于右结点
    						bIndex++;//记住右结点的值
    					}
    				}
    				//左右节点比较完了,开始和更节点进行比较、左右节点的大小无所谓
    				if(data[t]<data[bIndex]){//如果节点的值比较大
    					swap(data,t,bIndex);//交换他们,保证更节点的值是最大的
    					t=bIndex;//现在t变成了当前节点的左节点或者是右结点
    				}else{
    					break;
    				}
    			}
    		}
    	}
    	private static void swap(int[] data,int i,int j){
    		int tmp=data[i];
    		data[i]=data[j];
    		data[j]=tmp;
    	}
    }

6.归并排序

所谓归并排序,主要的思想就是先分割,后合并。

设有两个有序的子序列array\[low...m\]，array\[m + 1...high\]，合并到一个局部的暂存序列temp中,合并完成后将temp复制回array\[low...high\]中,从而完成排序,在具体的排序过程如下,首先从两组数中选择较小的数存放到temp数组中,然后把剩余元素比较多的那组数取出,存放到temp数组中(也就是较大的数),最后将temp数组复制回array数组中完成排序。

归并排序的时间复杂度是O(nlogn),归并排序算法是稳定的。

<span style="color:#000000;">public class MergeSort {
    	public static void main(String[] args) {
    		
    		int [] a={4,2,1,6,3,6,0,-5,1,1};
    		mergesort(a,0,a.length-1);
    		for(int ok:a){
    			System.out.printf("%d ",ok);
    		}
    	}
    
    	private static void mergesort(int[] a, int start, int end) {
    		if(start<end){//两路
    			int mid=(start+end)/2; 
    			mergesort(a, start, mid);
    			mergesort(a, mid+1, end);
    			merge(a,start,mid,end);
    			for(int ok:a)
    			System.out.printf("%d ",ok);
    			System.out.println("");
    		}
    		
    	}
    	public static void merge(int[] data, int left, int center, int right) {  
    	     
    	    int [] tmpArr=new int[data.length];  
    	    int mid=center+1; //右边那个小数组的子数组 
    	    //third记录中间数组的索引  
    	    int third=left;  
    	    int tmp=left;  
    	    while(left<=center&&mid<=right){  
    	        //从两个数组中取出最小的放入中间数组  
    	        if(data[left]<=data[mid]){  
    	            tmpArr[third++]=data[left++];  
    	        }else{  
    	            tmpArr[third++]=data[mid++];  
    	        }  
    	    }  
    	    //剩余部分依次放入中间数组  
    	    while(mid<=right){  
    	        tmpArr[third++]=data[mid++];  
    	    }  
    	    while(left<=center){  
    	        tmpArr[third++]=data[left++];  
    	    }  
    	    //将中间数组中的内容复制回原数组  
    	   while(tmp<=right){  
    	        data[tmp]=tmpArr[tmp++];  
    	    }
    	      
    	    
    	   
    	   
    	}  
    
    }</span>

7.希尔排序

首先选择步长,步长我这里每次选择上一次长度的1/2,初始长度为数组长度,以本程序中的数据为例,首先将原来的数据分成:

4,2,1, 6,3

6,0,-1,1,1

两组

然后对每一列进行排序得到以下的结果:

4,0,-1,1,1

6,2, 1,6,3

第二次的步长为:2

分成以下的几组:

4,0

\-1,1

1,6

2,1

6,3

按照列进行排序:

\-1,0

1,1

2,1

4,3

6,6

然后按照步长为1进行排序(也就是最普通的插入排序)得到最后的结果

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

希尔排序的事件复杂度为O(nlog2n),算法是不稳定的.

public class ShellSort {
    	public static int[] a={4,2,1,6,3,6,0,-1,1,1};
    	public static void main(String[] args) {
    		int i;
    		int index=a.length;
    		System.out.println("排序前:");
    		for(int ok:a){
    			System.out.printf("%3s",ok);
    		}
    		System.out.println("");
    		shellsort(index);
    		System.out.println("排序后: ");
    		for(i=0;i<index;i++){
    			System.out.printf("%3s",a[i]);
    		}
    		System.out.println("");
    	}
    	public static void shellsort(int index){
    	int i,j,k;
    	int temp;
    	boolean change;
    	int datalength;
    	int pointer;
    	datalength=index/2;
    	while(datalength!=0){
    		//对各个集合进行排序
    		for(j=datalength;j<index;j++){
    			change=false;
    			temp=a[j];
    			pointer=j-datalength;
    			while(temp<a[pointer]){
    				a[pointer+datalength]=a[pointer];
    				pointer=pointer-datalength;//这个运行一次就一直是小于０的
    				change=true;
    				if(pointer<0||pointer>index)break;
    			}
    			a[pointer+datalength]=temp;
    			if(change){
    				System.out.println("排序中:");
    				for(k=0;k<index;k++){
    					System.out.printf("%3s",a[k]);
    				}
    				System.out.println("");
    			}
    		}
    		datalength/=2;
    	}
    	}
    		
    }

8.快速排序

在进行快速排序之前,我们首先要选取一个基准数,这个基准数的选择比较随意,一般选择原数组中的第一个数即可。然后我们需要做的就是将比基准数小的数放到左边,比基准数大的数据放到右边。

首先我们定义两个哨兵,guardi和guardj,开始的时候把guardi指向数组的最低位,把guardj指向数组的最高位,因为我们设置的基准数在数组的最左边,所以guardj需要先走,不然我们会失去基准数,guardj从右往左找到第一个比基准数小的元素，然后停下,随后guardi从右往左找寻第一个比自己小的数,然后停下,停下之后我们立即交换左右两个数,继续执行上述步骤,直到两个哨兵相遇(这时候这个位置上的数一定会比基准数小),循环结束,将基准数和左右哨兵相遇的那个位置上的数交换,这样我们就以基准数为界,将所有的数据分成左右两部分,然后我们再将左右两部分分别进行递归,直到排序完成。

快速排序在最理想情况下时间复杂度是 O(nlogn)最差的情况下是O(n^2)，算法是不稳定的。

public class QuickSort {
    	public static void quicksort(int[] source,int low,int high){
    		int guardi,guardj,x;
    		if(low<high){
    			guardi=low;
    			guardj=high;
    			x=source[guardi];//选取第一个基准数
    			while(guardi!=guardj){
    				while(guardi<guardj&&source[guardj]>=x){//哨兵j从从右向左寻找比基准数小的元素,然后停下
    					guardj--;
    				}
    				while(guardi<guardj&&source[guardi]<=x){//哨兵i从左向右找寻比基准数大的数,然后停下
    					guardi++;
    				}
    				//停下之后立即交换两个左右两个数
    				if(guardi<guardj){
    					int temp=source[guardi];
    					source[guardi]=source[guardj];
    					source[guardj]=temp;
    					
    					
    				}
    			}
    			//跳出while循环表示两个哨兵在同一个位置上了,那么立即将基准数交换
    			source[low]=source[guardj];
    			source[guardj]=x;
    			//对左右两边的数据进行递归
    			quicksort(source,low,guardi-1);
    			quicksort(source,guardi+1,high);
    			
    		}
    	}
    
    	public static void main(String[] args) {
    		
    			int[] a={1,4,5,800,4,7,8,-2};
    			quicksort(a, 0, a.length-1);
    			for(int ok:a){
    				System.out.printf("%d ",ok);
    			}
    	}
    
    }

以上就是我对一些常见的排序算法的一些总结,本来想每个算法都配一个图例,但是自己不会做那种图,如果有时间的话再补上~~

附:

![21457204_1326898064RUxx.jpg][]

[08015657_WTZ5.gif]: /images/20220719/8a9cbd7fdc024f00a957719cb2786c09.png
[21457204_1326898064RUxx.jpg]: http://blog.chinaunix.net/attachment/201201/18/21457204_1326898064RUxx.jpg