排序算法总结---java面试

- 日理万妓 2022-09-23 08:17 122阅读 0赞

**总结了冒泡排序、选择排序、插入排序、堆排序、快速排序、归并排序、topk排序**

工具类：

public class ArrayUtils {
    
    	public static void printArray(int[] array) {
    		// TODO Auto-generated method stub
    		for (int i = 0; i < array.length; i++) {
    			System.out.print(array[i]+" ");
    		}
    	}
    
    	public static void exchangeElements(int[] array, int i, int i2) {
    		
    		// TODO Auto-generated method stub
    		int temp = array[i];
    		array[i] = array[i2];
    		array[i2] = temp;
    		
    	}
        
    }

1.冒泡排序

package sort;
    public class BubbleSort {
    	public static void bubbleSort(int a[]) {
    		int temp = 0;
    		for (int i = 0; i < a.length; i++) {
    			for (int j = 0; j < a.length - 1 - i; j++) {
    				if (a[j] > a[j + 1]) {
    					temp = a[j];
    					a[j] = a[j + 1];
    					a[j + 1] = temp;
    				}
    			}
    		}
    
    	}
    
    	public static void main(String[] args) {
    		int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35,
    				25, 53, 51 };
            bubbleSort(a);
    		for (int i = 0; i < a.length; i++)
    			System.out.println(a[i]);
    
    	}
    
    }

2.插入排序

![Center][]

public class insert{  //比喻成摸牌。从0开始但是手中的牌是拍好的
    	
    	 public static void insertSort(int[] a) {
    	 
    	 int length=a.length; //数组长度  
         int j;               //当前值的位置  
         int i;               //指向j前的位置  
         int key;             //当前要进行插入排序的值  
         //从数组的第二个位置开始遍历值  
         for(j=1;j<length;j++){  
             key=a[j];  
             i=j-1;  
             //a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移  
             while(i>=0 && key<a[i]){  
                 a[i+1]=a[i]; //将a[i]值后移  
                 i--;         //i前移  
             }//跳出循环(找到要插入的中间位置或已遍历到0下标)  
             a[i+1]=key;    //将当前值插入  
         }  
     } 
    	 
    	 
    	 public static void main(String[] args) {
    		int[] array = { 3, -1, 0, -8, 2, 1 };
    		ArrayUtils.printArray(array);
    		insertSort(array);
    		ArrayUtils.printArray(array);
    	}
    	
    }

3.选择排序

package sort;
    
    public class selectSort {
    
    	 public static void SelectionSort(int a[]){
    		   if (a == null || a.length <= 0) {  
    	            return;  
    	        }  
    	        int min;
    	        for (int j = 0; j < a.length-1; j++){
    	            min = j;
    	            for (int k = j+1; k < a.length; k++){
    	                if (a[k] < a[min])
    	                    min = k;
    	            }
    	            //swap(a[min], a[j]);
    	            int temp ;
    	    		temp = a[min];
    	    		a[min] =a[j] ;
    	    		a[j] = temp ;
    	        }
    	    }
    	
    	public static void main(String[] args) {
    		int a[] = {1,32,4,6,7,2} ;
    		SelectionSort(a);
    		for (int i = 0; i < a.length; i++) {
    			System.out.println(a[i]);
    		}
    	}
    	
    	
    }

4.堆排序

![Center 1][]

package sort;
    //堆是一种重要的数据结构，为一棵完全二叉树, 底层如果用数组存储数据的话，
    //假设某个元素为序号为i(Java数组从0开始,i为0到n-1), 如果它有左子树，
    //那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。
    //分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。
    //所谓堆排序就是利用堆这种数据结构来对数组排序，我们使用的是最大堆。处理的思想和冒泡排序，选择排序非常的类似，一层层封顶，
    //只是最大元素的选取使用了最大堆。最大堆的最大元素一定在第0位置，构建好堆之后，交换0位置元素与顶即可。堆排序为原位排序(空间小),
    //且最坏运行时间是O(n2)，是渐进最优的比较排序算法。
    
    //交换0位置元素与顶即可
    //堆排序的大概步骤如下:
    //
    //1.构建最大堆。
    //2.选择顶，并与第0位置元素交换
    //3.由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆(沉降法)，如果需要重复步骤2
    //堆排序中最重要的算法就是maxHeap，该函数假设一个元素的两个子节点都满足最大堆的性质(左右子树都是最大堆)，
    //只有跟元素可能违反最大堆性质，那么把该元素以及左右子节点的最大元素找出来，如果该元素已经最大，那么整棵树都是最大堆，
    //程序退出，否则交换跟元素与最大元素的位置，继续调用maxHeap原最大元素所在的子树。该算法是分治法的典型应用。具体代码如下:
    
    
    
    public class HeapSort2 {
    	public static void main(String[] args) {
    		int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
    
    		System.out.println("Before heap:");
    		ArrayUtils.printArray(array);
    
    		heapSort(array);
    
    		System.out.println("After heap sort:");
    		ArrayUtils.printArray(array);
    	}
    
    	public static void heapSort(int[] array) {
    		if (array == null || array.length <= 1) {
    			return;
    		}
    
    		buildMaxHeap(array);//构建最大堆，最大堆的任意子树根节点不小于任意子结点
    
    		for (int i = array.length - 1; i >= 1; i--) {//倒叙输出为升序
    			
    			ArrayUtils.exchangeElements(array, 0, i);//最大数字在顶端0的位置，依次将大的值写入array,从i开始就是array最后一个
    
    			maxHeap(array, i, 0);//重构
    		}
    	}
    
    	private static void buildMaxHeap(int[] array) {//1.构建最大堆。
    		if (array == null || array.length <= 1) {
    			return;
    		}
    
    		int half = array.length;
    		for (int i = half; i >= 0; i--) {
    			maxHeap(array, array.length, i);
    		}
    	}
    
    	private static void maxHeap(int[] array, int heapSize, int index) {//maxHeap调整堆(沉降法)
    		int left = index * 2 + 1;
    		int right = index * 2 + 2;
    
    		int largest = index;
    		if (left < heapSize && array[left] > array[index]) {//单课二叉树判断大小
    			largest = left;
    		}
    
    		if (right < heapSize && array[right] > array[largest]) {//right < heapSize,left < heapSize排除最后一排
    			largest = right;
    		}
    
    		if (index != largest) {
    			ArrayUtils.exchangeElements(array, index, largest);
    
    			maxHeap(array, heapSize, largest);//递归
    		}
    	}
    }

结果：

Before heap:  
9 8 7 6 5 4 3 2 1 0 -1 -2 -3 After heap sort:  
\-3 -2 -1 0 1 2 3 4 5 6 7 8 9

5.快速排序

![Center 2][]

package sort;
    
    public class quickSort2 {
    
    	//快速排序
    	static void quicksort(int s[], int l, int r)
    	{
    	    if (l < r)
    	    {
    			//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1有的书上是以中间的数作为基准数的，要实现这个方便非常方便，直接将中间的数和第一个数进行交换就可以了。
    	        int i = l, j = r, x = s[l];//风之思想加+挖坑，左右岗哨
    	        while (i < j)//数组大于2
    	        {
    	            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
    					j--;  //没找到就继续指针向左
    	            if(i < j) 
    					s[i++] = s[j];//找到后坑里填进去，填进去另一侧
    				
    	            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
    					i++;   //没找到就继续指针向右
    	            if(i < j) 
    					s[j--] = s[i];
    	        }
    	        s[i] = x;//相遇为止第一个数基准填进来
    	        quicksort(s, l, i - 1); // 递归调用 
    	        quicksort(s, i + 1, r);
    	    }
    	}
    	
    	public static void main(String[] args) {
    		int a[] = {1,3,4,6,7,4,9,3} ;
    		quicksort(a,0,a.length-1);
    		for (int i = 0; i < a.length; i++) {
    			System.out.println(a[i]);
    		}
    		
    	}
    
    	
    }

6.归并排序

![Center 3][]

package sort;
    
    public class mergerSort2 {
    
    static void merge(int arr[], int L, int M, int R) {//合并算法
        int LEFT_SIZE = M - L;//left array size
        int RIGHT_SIZE = R - M + 1;
    //    int left[LEFT_SIZE];
    //    int right[RIGHT_SIZE];
        int left[] = new int[LEFT_SIZE];
        int right[] = new int[RIGHT_SIZE];
        int i, j, k;
        
        // 1. Fill in the left sub array
        for (i=L; i<M; i++) {
            left[i-L] = arr[i];//sub array begin from 0
        }
        // 2. Fill in the right sub array
        for (i=M; i<=R; i++) {
            right[i-M] = arr[i];//sub array begin from 0
        }
        
        // 3. Merge into the original array
        i = 0;  j = 0;  k = L;//k point to the left array
        while (i < LEFT_SIZE && j < RIGHT_SIZE) {//没有到达子矩阵的顶端，这时比较左右矩阵如果左面小arr[k]位置放入左面值，即达到取晓得放入新的矩阵，i，j,k指针各自加上1
            if (left[i] < right[j]) {
                arr[k] = left[i];
                i++;
                k++;
            }
            else {
                arr[k] = right[j];
                j++;
                k++;
            }
        }
        
        while (i < LEFT_SIZE) {//一边到达了顶端，那么如果另一方还没到直接放入新矩阵
            arr[k] = left[i];
            i++;
            k++;
        }
        while (j < RIGHT_SIZE) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
    
    static void mergeSort(int arr[], int L, int R) {//分治+归并！！！！
        if (L == R) {//分支的结束为只有一个
            return;
        }
        else {
            int M = (L + R) / 2;
            mergeSort(arr, L, M);
            mergeSort(arr, M+1, R);
            merge(arr, L, M+1, R);
        }
    }
    
    public static void main(String[] args) 	
    {
        int arr[] = {6, 8, 10, 9, 4, 5, 2, 7,3};
        int L = 0;
        int R = arr.length;
        mergeSort(arr, L, R);
        
        int i;
        for (i=0; i<=R; i++) {
            System.out.println(arr[i]);
        }
     }
    	
    }

**top k---from http://www.cnblogs.com/big-sun/p/4085793.html**

在很多的笔试和面试中，喜欢考察Top K.下面从自身的经验给出三种实现方式及实用范围。

*  合并法

这种方法适用于几个数组有序的情况，来求Top k。时间复杂度为O(k\*m)。(m:为数组的个数）.具体实现如下：

/**
    * 已知几个递减有序的m个数组，求这几个数据前k大的数
    *适合采用Merge的方法,时间复杂度(O(k*m);
    */
    import java.util.List;
    import java.util.Arrays;
    import java.util.ArrayList;
    public class TopKByMerge{
     public int[] getTopK(List<List<Integer>>input,int k){
        int index[]=new int[input.size()];//保存每个数组下标扫描的位置;
        int result[]=new int[k];
        for(int i=0;i<k;i++){
           int max=Integer.MIN_VALUE;
           int maxIndex=0;
           for(int j=0;j<input.size();j++){
               if(index[j]<input.get(j).size()){
                    if(max<input.get(j).get(index[j])){
                        max=input.get(j).get(index[j]);
                        maxIndex=j;
                    }
               }
           }
           if(max==Integer.MIN_VALUE){
               return result;
           }
           result[i]=max;
           index[maxIndex]+=1;
           
        }
        return result;
     }

*  　快排过程法

快排过程法利用快速排序的过程来求Top k.平均时间复杂度为(O(n)).适用于无序单个数组。具体java实现如下：

/*
    *利用快速排序的过程来求最小的k个数
    *
    */
    public class TopK{
       int partion(int a[],int first,int end){
            int i=first;
            int main=a[end];
            for(int j=first;j<end;j++){
                 if(a[j]<main){
                    int temp=a[j];
                    a[j]=a[i];
                    a[i]=temp;
                    i++;
                 }
            }
            a[end]=a[i];
            a[i]=main;
            return i;    
       }
       void getTopKMinBySort(int a[],int first,int end,int k){
          if(first<end){
              int partionIndex=partion(a,first,end);
              if(partionIndex==k-1)return;
              else if(partionIndex>k-1)getTopKMinBySort(a,first,partionIndex-1,k);
              else getTopKMinBySort(a,partionIndex+1,end,k);
          }
       }
    public static void main(String []args){
          int a[]={2,20,3,7,9,1,17,18,0,4};
          int k=6;
          new TopK().getTopKMinBySort(a,0,a.length-1,k);
          for(int i=0;i<k;i++){
             System.out.print(a[i]+" ");
          }
       }
    }

*  采用小根堆或者大根堆

求最大K个采用小根堆，而求最小K个采用大根堆。

求最大K个的步奏：

1.      根据数据前K个建立K个节点的小根堆。
2.      在后面的N-K的数据的扫描中，

*  如果数据大于小根堆的根节点，则根节点的值覆为该数据，并调节节点至小根堆。
 *  如果数据小于或等于小根堆的根节点，小根堆无变化。

求最小K个跟这求最大K个类似。时间复杂度O(nlogK)(n:数据的长度),特别适用于大数据的求Top K。

/**
     * 求前面的最大K个 解决方案：小根堆 (数据量比较大（特别是大到内存不可以容纳）时，偏向于采用堆)
     * 
     * 
     */
    public class TopK {
        /**
         * 创建k个节点的小根堆
         * 
         * @param a
         * @param k
         * @return
         */
        int[] createHeap(int a[], int k) {
            int[] result = new int[k];
            for (int i = 0; i < k; i++) {
                result[i] = a[i];
            }
            for (int i = 1; i < k; i++) {
                int child = i;
                int parent = (i - 1) / 2;
                int temp = a[i];
                while (parent >= 0 &&child!=0&& result[parent] >temp) {
                    result[child] = result[parent];
                    child = parent;
                    parent = (parent - 1) / 2;
                }
                result[child] = temp;
            }
            return result;
    
        }
    
        void insert(int a[], int value) {
             a[0]=value;
             int parent=0;
             
             while(parent<a.length){
                 int lchild=2*parent+1;
                 int rchild=2*parent+2;
                 int minIndex=parent;
                 if(lchild<a.length&&a[parent]>a[lchild]){
                     minIndex=lchild;
                 }
                 if(rchild<a.length&&a[minIndex]>a[rchild]){
                     minIndex=rchild;
                 }
                 if(minIndex==parent){
                     break;
                 }else{
                     int temp=a[parent];
                     a[parent]=a[minIndex];
                     a[minIndex]=temp;
                     parent=minIndex;
                 }
             }
             
        }
    
        int[] getTopKByHeap(int input[], int k) {
            int heap[] = this.createHeap(input, k);
            for(int i=k;i<input.length;i++){
                if(input[i]>heap[0]){
                    this.insert(heap, input[i]);
                }
            
                
            }
            return heap;
    
        }
    
        public static void main(String[] args) {
            int a[] = { 4, 3, 5, 1, 2,8,9,10};
            int result[] = new TopK().getTopKByHeap(a, 3);
            for (int temp : result) {
                System.out.println(temp);
            }
        }
    }

[Center]: /images/20220721/544508e223b54d44b37482c3a0f681a8.png
[Center 1]: /images/20220721/e8621f6c07474db3a1720369f134d98f.png
[Center 2]: /images/20220721/e5f709a5183145abb890523c4cddf739.png
[Center 3]: /images/20220721/7be5a99609c64a3090404d58f7973168.png