几种排序算法的Java实现

心已赠人 2022-04-25 08:42 249阅读 0赞

最近对几种排序算法进行了梳理  
**1、冒泡排序**

*  算法思想： 依次和相邻的数进行比较，这样每一次出发都把最大的放到了最后一个
 *  时间复杂度 n的平方
 *

\*实现 代码

public  int [] bubbleSort (int[] a ){
    	//冒泡排序
    
    	//记得对一个数组进行排序前先判断这个诗数组是不是为空
    	
    	if (a.length ==0) {	
    		return a;
    	}
    	
    	for (int i = 0; i < a.length-1; i++) {
    		for (int j = 0; j < a.length-1-i; j++) {
    			
    			if (a[j+1]<a[j]) {
    				int temp = a[j+1];
    				a[j+1] = a[j];
    				a[j] = temp;
    				
    			}
    			
    		}
    	}
    	
    	
    	  //冒泡排序的优化利用标记比较不用排序的位置
    	 
    	 
    	 /* boolean flag = false;
    	for (int i = 0; i < a.length-1; i++) {
    	     
    	     flag = false;
    	
    		for (int j = i; j < a.length-1-i; j++) {
    			
    			if (a[j+1]<a[j]) {
    				int temp = a[j+1];
    				a[j+1] = a[j];
    				a[j] = temp;
    				
    				flag = true;	
    			}
    			if (flag =false){
    			  break;
    			}
    		}
    	}*/
    	 
    	return a;
    	
    }

**2 快速排序**  
思想：  
（1）找到一个key值  
（2）先走一趟，进行交换，把比key小的都放到key前面，把比key大的都放到key后面，key和i的位置互换  
（3）这样调用递归分别对key值前后的分段数据再进行排序

*/ 
    public  int[] quicksort (int [] a){
    	
    	
    	//int [] b = new int[ARRY_LENGT];
    	if (a.length>0) {
    		 quicksort(a, 0 , a.length-1);
    	 	
    	}
    			
    	return a;		
    }
    
    
    private void quicksort(int[] a, int low, int high) {
    	//1.找到递归算法的出口
    	if(low>high){
    		return;
    	}
    	 int start = low;
         int end = high;
         int key = a[low];
         
         
         while(end>start){
             //从后往前比较
             while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                 end--;
             if(a[end]<=key){
                 int temp = a[end];
                 a[end] = a[start];
                 a[start] = temp;
             }
             //从前往后比较
             while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
             if(a[start]>=key){
                 int temp = a[start];
                 a[start] = a[end];
                 a[end] = temp;
             }
         //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
         }
         //递归
         if(start>low) quicksort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
         if(end<high) quicksort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
     }

**3.插入排序**  
/\*  
插入排序，插入排序是一种简单直观的排序算法。  
它的工作原理是通过构建有序序列，对于未排序数据，  
在已排序序列中从后向前扫描，找到相应位置并插入。  
插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，  
为最新元素提供插入空间。  
算法分析 最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)  
\*/

public static int[] insertSort(int[] ins){
    	
    		for(int i=1; i<ins.length; i++){		
    			int temp = ins[i];//保存每次需要插入的那个数		
    			int j;			
    			for(j=i; j>0&&ins[j-1]>temp; j--){//这个较上面有一定的优化	
    				ins[j] = ins[j-1];//把大于需要插入的数往后移动。最后不大于temp的数就空出来j		
    				}			
    			ins[j] = temp;//将需要插入的数放入这个位置		
    				}		
    		return ins;		
    			
    		}

**4.希尔排序**

希尔排序(希尔排序是插入排序的一种优化)，将所有的数据记性分段，然后按列进行排序，依次减小排序的成本

（1）分组  
（2）列排序  
（3）分组步数减小，再次分组  
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)　  
\*/  
public int \[\] shellSort(int \[\] a)\{  
int len = a.length;  
int tem,gap=len/2; //gap就是长度的一半，步长

while (gap>0) {
    		for (int i =gap; i < len ; i++) {
    			
    			tem = a[i];
    			
    			int preindex = i-gap;
    			
    			while (preindex>0&&a[preindex] > tem) {
    				
    				a[preindex+gap] = a[preindex];
    				preindex -= gap;
    			}
    			 a[preindex+gap]=tem;
    		}
    		
    	}
    	
    	return a;
    	
    }

**5.选择排序**

*  思想：（1）们每次排序找到最小的数，记录原始位置
 *      （2）置换到应该有的位置
 *  
 *  平均时间复杂度 n2，最坏时间复杂度n2
 *  \*/
    
    public int \[\] selectSort(int \[\] a)\{  
    for (int i = 0; i < a.length-1; i++) \{  
    int k=i;  
    for (int j = k+1; j < a.length; j++) \{
    
        if (a[j]<a[k]) {
         			k=j; //记下目前查找到的最小值所对应的位置
         		}
         		//内层一次循环结束开始进行比较
         		if (k!=i) {
         			int tem =a[i];
         			a[i]=a[k];
         			a[k]=tem;
         		}
         	}
         }
         
         return a;
    
    \}  
    主函数
    
    public static void main(String\[\] args) \{  
    // TODO Auto-generated method stub  
    sort mSort =new sort(); //new新的对象的同时调用构造函数进行初始化
    
        //冒泡排序
            long start=System.currentTimeMillis();	//获取系统当前时间
            System.out.print("冒泡排序:");		
            int  bubblesort[]=mSort.bubbleSort(mSort.CopyArrayData());	
            long end=System.currentTimeMillis();		//mInternalSort.printArray(bubblesort);