Java基础学习之手写插入、冒泡和快速排序

在Java面试时，有时面试官会让你手写几种排序，比如写一个插入排序、写一个冒泡排序和选择排序，甚至问你是否有更快速和高效的排序方式，对于大多数人来说也许并不陌生，但具体要怎么写可能有点困难。这几种排序背后代表的也算是几种思想，虽算不上高深的算法，但也是进入算法的入门级别，这次我们可以来一起学习下，掌握它不在话下。

插入排序可以理解为抓牌的过程，每次抓牌后将此张牌和手里已排好序的牌依次比较并插入，插入即交换的过程，两层循环可以搞定。

	// 可以理解l=0,r=length
 	for(int i=l+1;i0&&A[j] 
时间复杂度可以看到平均为O(n^2)
 
 
选择排序： 
选择排序就是我们找出最大值丢到最后面，以此类推
 
  	
    private void selectSort(int[]A,int l,int r){
        for(int i=r-1;i>l;i--){
            int maxIndex=maxIndex(A,0,i+1);
            swap(A,maxIndex,i);
        }
    }
    private int maxIndex(int[]A,int l,int r){
        int max=Integer.MIN_VALUE;
        int index=l;
        for(int j=l;jmax){
                max=A[j];
                index=j;
            }
        }
        return index;
    }
 
时间复杂度可以看到平均为O(n^2)
 
 
冒泡排序： 
冒泡排序就是每次两两比较，确认最小的或最大的往一边丢。比如针对某序列，
 
 
 	
    private void bubbleSort(int[]A,int l,int r){
        // 1 5 2 4 6
        // 1 2 4 5 6
        for(int i=r-1;i>l;i--){
            for(int j=0;j<=i-1;j++){
                if(A[j]>A[j+1]){
                    swap(A,j,j+1);
                }
            }
        }
    }
 
时间复杂度可以看到平均为O(n^2)
 
 
合并排序-分治策略： 
每次都需要两层循环可能对于大数据量性能不是很好，有没有更好性能的排序呢？当然有，比如我们可以通过分治策略来实现一种合并排序。
 
 其实理解起来很简单：就是将某数组平均分成两段A、B,针对数组A排好序，数组B排好序，然后合并。这里如何对A,B如何排序呢，我们可以不断二分下去，形成了递归，直至单个返回。
 
    
    private void mergeSort(int[] A,int l,int r) {
        if (r - l <= 1) return;
        int m = (l + r + 1) / 2;
        // |--l--| m |--r--|
        mergeSort(A, l, m);
        mergeSort(A, m, r);
        merge(A, l, m, r);
    }
    private void merge(int[] A,int l,int m ,int r){
        int[] B=Arrays.copyOfRange(A,l,m+1);
        int[] C=Arrays.copyOfRange(A,m,r+1);
        B[B.length-1]=C[C.length-1]=Integer.MAX_VALUE;
        int i=0,j=0;
        for(int k=l;k 
时间复杂度为O(nlogn)，具体推导可参考这篇文章
 https://blog.csdn.net/liangjiabao5555/article/details/89670082
 
快速排序 
快速排序可以理解为合并排序的一种特殊情况，但又确实能起到高速排序的效果。
 总体思想是设置一个比较位，例如第一个元素x=27，在i=1，j=length-1(假如数组A长度为length)设置两个标志位用于比较，若A[i]>x，则将A[i]丢到j位置上，否则i++，直至i=j为止。
 
 
    
    private void quickSort(int[] A,int l,int r){
        if(r-l<=1) return;
        int m=partion(A,l,r);
        quickSort(A,l,m);
        quickSort(A,m+1,r);
    }

    
    private int partion(int[] A,int l,int r){
    // x|--l--|m|--r--|
        int x=A[l];
        int i=l+1;
        int j=r;
        while(i!=j) {
            if (A[i] < x) {
                i++;
            } else {
                swap(A, i, --j);
            }
        }
        swap(A,i-1,l);
        return i-1;
    }
 
快速排序时间复杂度为：O(nlogn)
 分别用上述排序方式测试10000个随机数据，花销时间如下：
 
 可见利用分治策略的快速排序和合并排序速度确实比较快。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4996598.html