手写常用排序算法(插入,希尔,快排,选择,堆排序,归并,基数,桶排序)，java实现

冷不防 2022-05-13 10:56 129阅读 0赞

在排序算法的复习当中，有些算法还是比较难理解的，好在以前打下的基础，再次学习轻松很多，下面记录下手写常用的排序算法。如标题所示。每个排序加了一些便于我自己理解的短语，希望大家在看这边文章时，已经对排序算法有所理解。

### *直接插入排序的性能分析*： ###

1. 最好情况：O(n)   
2. 平均情况：O(n^2)   
3. 最坏情况：O(n^2)   
空间复杂度：O(1)   
稳定性：稳定(相同元素的相对位置不会改变)

### *希尔排序（第一个突破*O(n^2)的排序算法*）的性能分析：* ###

会根据增量的不同而不同，一般来说：   
  
1. 最好情况：O(n^1.3)   
2. 最坏情况：O(n^2)   
空间复杂度：O(1)   
稳定性：不稳定(相同元素的相对位置会改变)

### *快速排序的性能分析：* ###

1. 最好情况：O(nlog2(n))   
2. 平均情况：O(nlog2(n))   
3. 最坏情况：O(n^2)   
空间复杂度：O(log2(n))   
稳定性：不稳定(相同元素的相对位置会改变)

### 简单选择排序的性能分析： ###

1. 最好情况：O(n^2)   
2. 平均情况：O(n^2)   
3. 最坏情况：O(n^2)   
空间复杂度：O(1)   
稳定性：不稳定(相同元素的相对位置会改变)

### 堆排序的性能分析： ###

1. 最好情况：O(nlog2(n))   
2. 平均情况：O(nlog2(n))   
3. 最坏情况：O(nlog2(n))   
空间复杂度：O(1)   
稳定性：不稳定(相同元素的相对位置会改变)

### 基数排序性能分析： ###

1. 最好情况：O(d(n+r))   
2. 平均情况：O(d(n+r))   
3. 最坏情况：O(d(n+r))   
空间复杂度：O(n+r)   
稳定性：稳定

package com.me.sorts;
    
     
    public  class Sorts {
    	
    	/**
    	 * 插入排序（将无序区的依次插入到有序区合适的位置）
    	 * @param a 
    	 */
    	public static void InsertSort(int[] a) {
    		if (a==null || a.length<=0) { //排空
    			System.out.println("数组为空");
    			return ;
    		}
     
    		int temp=0; //暂存要插入的元素
    		int j=0;
    		for (int i = 1,len=a.length; i <len; i++) {  //遍历数组
    			temp=a[i];
    			j=i-1;   
    			for (; j>=0 && a[j]>temp;j--) {  //如果a[i]之前的数比要插入的temp大,该数左移。注意j>=0
    				a[j+1]=a[j];
    			}
    			a[j+1]=temp; //当循环结束，也就是temp比a[j]大或者相等，或者最小时（j=-1）,插入到a[j]后面，是j++的原因是因为循环结束时执行了一次j--
    		}
    	}
     
    	/**
    	 * 希尔排序 （将整个序列划分为若干个子序列，并对子序列进行选择排序，待整个序列基本有序时再进行一次整体的选择排序 ）
    	 * @param a
    	 */
    	public static void shellSort(int[] a) {
    		if (a==null || a.length<=0) { //排空
    			System.out.println("数组为空");
    			return ;
    		}
    		int temp=0; //暂存要插入的元素
    		int len=a.length;
    		int j=0;
    		for (int d = len/2; d>0; d/=2) { //取d/2来分割排序记录
    			for (int i = d; i<len; i++) {//从d开始，循环到结束
    				temp=a[i];
    				j=i-d;  //取第前d个元素作为比较
    				for (; j>=0 && a[j]>temp; j-=d) { //连续以d为分割比较
    					a[j+d]=a[j];
    				}
    				a[j+d]=temp; //插入
    			}
    		}
    	}
     
    	/**
    	 * 冒泡排序改进版 （将大的元素向后移，小的向前移，并记录每次交换位置，
    	 *   下趟排序只排序初始到上次交换的位置）
    	 * @param a
    	 */
    	public static void bubbleSort(int[] a) {
    		int exchange=a.length-1;
    		int bound=0;
    		while (exchange!=0) {   //当上一次排序有记录交换时，说明还不是有序的
    			bound=exchange;
    			exchange=0;
    			for (int i = 0; i < bound; i++) { //一趟冒泡排序的区间是[1,bound]
    				if (a[i]>a[i+1]) {
    					a[i]=a[i]+a[i+1];
    					a[i+1]=a[i]-a[i+1];
    					a[i]=a[i]-a[i+1];
    					exchange=i; //记录每一次交换的位置
    				}
    			}
    		}
    	}
     
    	/**
    	 * 快速排序算法 （两边同时开始扫描，哪边小交换哪边。得出结果继续划分）
    	 * @param a
    	 * @param first
    	 * @param end
    	 */
    	public static void quickSort(int[] a,int first,int end) {
    		if (first<end) {
    			int pivot=partition(a, first, end); //开始对区间进行排序，返回最终的轴值
    			quickSort(a, first, pivot-1);       //递归排序左区间，轴值不需要参与排序
    			quickSort(a, pivot+1, end);         //递归排序右区间
    		}
    	}
    	/**
    	 * 快速排序一次划分算法 
    	 * @param a
    	 * @param first
    	 * @param end
    	 * @return
    	 */
    	public static int partition(int a[],int first,int end) {
    		int i=first,j=end;
    		while (i<j) {
    			while (i<j && a[j]>=a[i]) { //从右侧开始扫描，直到找到右侧的比左侧小的数，然后交换位置
    				j--;
    			}
    			if (i<j) {  //交换位置
    				a[i]=a[i]+a[j];
    				a[j]=a[i]-a[j];
    				a[i]=a[i]-a[j];
    				i++;
    			}
     
    			while (i<j && a[j]>=a[i]) { //从左侧开始扫描，直到找到右侧的比左侧小的数，然后交换位置
    				i++;
    			}
    			if (i<j) { //交换位置
    				a[i]=a[i]+a[j];
    				a[j]=a[i]-a[j];
    				a[i]=a[i]-a[j];
    				j--;
    			}
    		}
    		return i;  //轴值记录的最终位置
    	}
     
    	/**
    	 * 选择排序 （每次从未排序区域循环寻找最小元素放到已排序的区域）
    	 * @param a
    	 */
    	public static void selectSort(int[] a) {
    		int index=0;
    		for (int i = 0,len=a.length; i < len-1; i++) {
    			index=i; //存储要交换的位置
    			for (int j = i+1; j < len; j++) { //每次循环寻找最小的
    				if (a[j]<a[index]) {
    					index=j;
    				}
    			}
    			if (index!=i) { //需要交换
    				a[i]=a[i]+a[index];
    				a[index]=a[i]-a[index];
    				a[i]=a[i]-a[index];	
    			}
    		}
    	}
    	
    	/**
    	 * 堆排序 （先构建初始大项堆，之后每次交换堆顶元素与末尾元素并调整堆）
    	 * @param a
    	 */
    	public static void heapSort(int[] a ) {
    		int len=a.length;
    		for (int i = len/2-1; i >=0; i--) { //初始化建大根堆
    			sift(a,i,len);
    		}
    		
    		 //调整堆结构+交换堆顶元素与末尾元素（栈顶元素最大，末尾元素次大）
            for(int i=len-1;i>0;i--){
            	a[0]=a[i]+a[0];
    			a[i]=a[0]-a[i];
    			a[0]=a[0]-a[i];
                sift(a,0,i);//重新对堆进行调整
            }
    		
    	}
    	
        /**
         * 堆排序，调整堆方法
         * @param a
         * @param i
         */
    	public static void sift(int[] a, int k,int m) {
    		int i=k;
    		int j=2*i+1;
    		while (j<m) {
    			if (j+1<m && a[j]<a[j+1]) { //比较j的左右孩子，指向最大的
    				j++;
    			}
    			if (a[i]>a[j]) { //根节点已经大于左右孩子的较大者，排序结束
    				break;
    			}else {
    				//将根节点与结点j交换
    				a[i]=a[i]+a[j];
    				a[j]=a[i]-a[j];
    				a[i]=a[i]-a[j];
    				i=j; j=2*i+1; 
    			}
    			
    		}
    	}
    	
    	/**
    	 * 归并排序入口   （先划分为一个个的数，接着两两将有序序列归并为有序序列）
    	 * @param arr
    	 */
    	public static void mergeSort(int[] arr) {
    		int[] temp = new int[arr.length]; //临时数组
    		mergeSort(arr,0,arr.length-1,temp); 
    	}
    	
    	/**
    	 * 
    	 * @param arr 要排序的数组
    	 * @param left 左坐标
    	 * @param right 右坐标
    	 * @param temp 临时数组
    	 */
    	public static void mergeSort(int[] arr,int left,int right,int[] temp) {
    		if (left<right) { 
    			int mid = (left+right)/2;
    			mergeSort(arr,left,mid,temp); //递归划分左边区域
    			mergeSort(arr,mid+1,right,temp); //递归划分右边区域
    			merge(arr, left, mid, right, temp); //将两个已排序的子序列归并
    		}
    	}
    	
    	/**
    	 * 一次归并算法
    	 * @param arr
    	 * @param left
    	 * @param mid
    	 * @param right
    	 * @param temp
    	 */
    	public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
    		int i=left;
    		int j=mid+1;
    		int t=0;
    		while (i<=mid && j<=right) {
    			if (arr[i]<=arr[j]) { //<=
    				temp[t++]=arr[i++];
    			}else {
    				temp[t++]=arr[j++];
    			}
    		}
    		
    		while (i<=mid) {//第一个子序列还没有处理完
    			temp[t++]=arr[i++];
    		}
    		while (j<=right) {//第二个子序列还没有处理完
    			temp[t++]=arr[j++];
    		}
    		t=0;
    		while (left<=right) { //将temp中的元素全部拷贝到原数组中
    			arr[left++]=temp[t++];
    		}
    		
    	}
     
    	public static void main(String[] args) {
    		int[] a = {3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		InsertSort(a);
    		System.out.print("直接插入排序：");
    		for(int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + " ");
    		}
     
    		System.out.println();
    		int[] b={3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		shellSort(b);
    		System.out.print("希尔排序：");
    		for(int i = 0; i < b.length; i++) {
    			System.out.print(b[i] + " ");
    		}
     
    		System.out.println();
    		int[] c={3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		bubbleSort(c);
    		System.out.print("冒泡排序改进版：");
    		for(int i = 0; i < c.length; i++) {
    			System.out.print(c[i] + " ");
    		}
     
    		System.out.println();
    		int[] d={3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		quickSort(d, 0, d.length-1);		
    		System.out.print("快速排序：");
    		for(int i = 0; i < d.length; i++) {
    			System.out.print(d[i] + " ");
    		}
    		
    		System.out.println();
    		int[] e={3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		selectSort(e);
    		System.out.print("选择排序：");
    		for(int i = 0; i < e.length; i++) {
    			System.out.print(e[i] + " ");
    		}
    		
    		System.out.println();
    		int[] f={3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		heapSort(f);
    		System.out.print("堆排序：");
    		for(int i = 0; i < f.length; i++) {
    			System.out.print(f[i] + " ");
    		}
    		
    		System.out.println();
    		int[] g={3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
    		mergeSort(g);
    		System.out.print("归并排序：");
    		for(int i = 0; i < g.length; i++) {
    			System.out.print(g[i] + " ");
    		}
    	}
    }

![70][]

### 基数排序 ###

/**
     * 待排序数组中的值先按个位数入桶，出桶时覆盖原数组中的数据，再按十位数入桶，再出桶.....
     * @Description: 基数牌组java实现
     * @Version: 1.0
     */
    public class Radixsort {
        /**
         *  排序方法
         * @param array 要排序的数组
         * @param d //最大的位数
         */
        public static void radixsort(int[] array,int d){
            int n=1; //代表除的位数，1,10,100......
            int k=0; //控制输出的下标
            int length = array.length; //数组长度
            int[][] bucket = new int[10][length]; //桶排序所用的桶子
            int[] order = new int[length]; //记录每个桶子的长度
            while (n < d){
                for (int num:array){ //循环入桶
                    int digit=(num/n)%10; //计算入哪一个桶
                    bucket[digit][order[digit]]=num; //入桶
                    order[digit]++; //相应桶里面的数的个数加1
                }
                for (int i=0;i<length;i++){ //出桶，覆盖到原数组
                    if(order[i]!=0){ //说明这个桶里有数据
                        for (int j=0;j<order[i];j++){  //出桶
                            array[k]=bucket[i][j];
                            k++;
                        }
                    }
                    order[i]=0; //将这个桶的个数重置为0
                }
                n*=10; //除的位数*10
                k=0; //将k置0，用于下一轮保存位排序结果
            }
        }
    
        public static void main(String[] args) {
            int[] A=new int[]{73,22, 93, 43, 55, 14, 28, 65, 39, 81};
            radixsort(A,100);
            for(int num:A)
            {
                System.out.print(num+",");
            }
        }
    }

### 桶排序 ###

/** 选出待排序数组中的最大值 max，创建一个长度为max的数组bucket，将带待排序的数组的值作为
     * 这个bucket的下标，而bucket值作为这个值的个数。最后将桶中的数组按顺序取出
     * @Description:桶排序
     * @Version: 1.0
     */
    public class BucketSort {
    
        /**
         *
         * @param a 需要排序的数组
         * @param max 数组中的最大数
         */
        public static void bucketSort(int[] a,int max){
            int[] buckets;
    
            if (a==null || max<1)
                return;
    
            buckets = new int[max]; //创建一个最大数为max的bucket，初始化为0
    
            // 计算每个桶中数的个数
            for(int i = 0; i < a.length; i++)
                buckets[a[i]]++;
    
            //排序
            for (int i = 0,j = 0;i<max;i++){
                while ((buckets[i]--)>0) {
                    a[j++]=i;
                }
            }
            buckets=null;
        }
        public static void main(String[] args) {
            int i;
            int a[] = {8,2,3,4,3,6,6,3,9};
    
            System.out.printf("before sort:");
            for (i=0; i<a.length; i++)
                System.out.printf("%d ", a[i]);
            System.out.printf("\n");
    
            bucketSort(a, 10); // 桶排序
    
            System.out.printf("after  sort:");
            for (i=0; i<a.length; i++)
                System.out.printf("%d ", a[i]);
            System.out.printf("\n");
        }
    }

[70]: /images/20220513/837b52ece1ae477bad6db97251ebfb51.png