关于几种最常见的排序算法

快排

一般来说，快排是面试手撕代码时考的最多的。
不稳定。
空间复杂度为O(n^2)——O(nlogn)。
时间复杂度为O(n^2)——O(nlogn)，当排序正确时，时间复杂度最高。

算法思想

分治策略。挖坑填数＋分治法。
1.先从数列中取出一个数作为基数，一般取数列的第一个
2.将比这个数大的放在右边，小于等于的数放在左边
3.重复

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
	Created on 2017年12月5日
	@author: Scorpio.Lu
**/
	public static void main(String[] args) {
		int[] data=new int[]{45,67,33,21};
		quickSort(data, 0, data.length-1);
		System.out.println(Arrays.toString(data));
		
	}
	//递归
	private static void quickSort(int[] data, int i, int j) {
		int left=i,right=j;
		int x=data[left];  //取第一个数，挖坑
		while(i<j){
			//从数组尾部(j)开始遍历，如果发现小于等于x的数，就挪到坑里，这时候(j)就是一个新坑
			while(i<j && data[j]>x){
				j--;
			}
			if(i<j){
				data[i++]=data[j];
			}
			//从数组顶部(i)开始遍历，如果发现大于x的数，就挪到坑里，这时(i)就是一个新坑
			while(i<j && data[i]<x){
				i++;
			}
			if(i<j){
				data[j--]=data[i];
			}
		}
		data[i]=x;//补坑
		//一遍完成，继续排序坑左边的
		if(left<i-1){
			quickSort(data,left, i-1);
		}
		//排序坑右边的
		if(i+1<right){
			quickSort(data, i+1, right);
		}
		
	}

堆排序

一般来说，堆排序面试时问的也挺多的。
不稳定。
空间复杂度为O(1)。
时间复杂度为O(nlogn)。

算法思想

重复建堆，每次输出最大值。
如何找到堆中的最大值呢？从堆中取最后一个右子节点，跟左子节点比较。
大的值再跟父节点比较，如果大于父节点，交换二者。
以此类推，最大值“冒泡”到了根节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
	Created on 2017年12月5日
	@author: Scorpio.Lu
**/
	public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
        int arrayLength=a.length;  
        //循环建堆  
        for(int i=0;i<arrayLength-1;i++){  
            //建堆  
            buildMaxHeap(a,arrayLength-1-i);  
            //交换堆顶和最后一个元素  
            swap(a,0,arrayLength-1-i);  
            System.out.println(Arrays.toString(a));  
        }  
    }
	/**
	 * 建堆
	 * @param a
	 * @param i
	 */
    private static void buildMaxHeap(int[] a, int lastIndex) {
    	//index是最后一个父节点
		int index=(lastIndex-1)/2;
		for(int i=index;i>=0;i--){
			if(2*i+1<=lastIndex){
			 int biggerIndex=2*i+1;
			 if(2*i+2<=lastIndex){
				 biggerIndex=a[biggerIndex]>a[biggerIndex+1]?biggerIndex:biggerIndex+1;
			}
			 if(a[biggerIndex]>a[i]){
				 swap(a, biggerIndex, i);
			 }
			
		}
		}
		
	}
	    //交换
    private static void swap(int[] data, int i, int j) {  
        int tmp=data[i];  
        data[i]=data[j];  
        data[j]=tmp;

关于面试

一般来说，大厂就手撕这两个。然后会问到一些延伸的问题
比如：求Top3大的数。
堆排序可以解决。快排也可以，但是用快排时要考虑到一个问题，是不是要全部排完？
面试狼厂时又有个拓展的问题。如果数据量以亿计又该怎么办？这时候数据是没有办法一次性读入内存的，用快排和堆排序是不行的。

作者 [Scorpio.Lu]
2017 年 12 月 5 日
转载请注明出处！