排序算法总结及面试题_面试题 内存空间有限 利用硬盘空间 排序

算法复杂度以及稳定性分析

直接插入排序

public static void insertSort(int[] arr){
	if(arr == null || arr.length <= 1) return; 
	for(int i=1;i<arr.length ;i++){
		int p=i;
		int temp=arr[p];
		while(p>0&&arr[p-1]>temp){
			arr[p]=arr[p-1];
			p--;
		}
		arr[p]=temp;
	}
}

public static void binaryInsertSort(int[] arr){
	if(arr == null || arr.length <= 1) return; 
	for(int i=1;i<arr.length ;i++){
		int temp=arr[i];
		int start=0,end=i;
		while(start<end){
			int mid=start+(end-start)/2;
			if(arr[mid]<=temp){
				start=mid+1;
			}else{
				end=mid;
			}
		}
		int p=i;
		while(p>end){
			arr[p]=arr[p-1];
			p--;
		}
		arr[p]=temp;
	}
}

public class ListNode{
	private int val;
	private ListNode next;
	public ListNode(int val){
		this.val=val;
	}
}
public static ListNode listInsertSort(ListNode head){
	ListNode myHead=new ListNode(-1);
	ListNode p=head,t,pre,post;
	while(p!=null){
		t=p;
		p=p.next;
		pre=myHead;
		post=myHead.next;
		while(post!=null&&post.val<=t.val){
			pre=pre.next;
			post=post.next;
		}
		t.next=post;
		pre.next=t;
	}
	return myHead.next;
}

func insertSortList(root *ListNode) *ListNode {
    var head *ListNode
    p := root
    for p!=nil {
        q := p
        p=p.Next
        q.Next = nil
        if head == nil {
            head = q
        } else {
            if head.Val > q.Val {
                q.Next = head
                head = q
            } else {
                pre := head
                post := head.Next
                for post!=nil && post.Val >= q.Val {
                    pre = post
                    post = post.Next
                }
                q.Next = post
                pre.Next = q
            }
        }
    }
    return head
}

希尔排序

基本思想：
直接插入排序中，如果元素X初始化时所处的位置为i，排序后所处位置为j，那么元素x必须要经过j-i-1(j>=i)次移动。而希尔排序中，我们先取一个小于n的整数d1作为第一个增量，把数据的全部记录分组。所有距离为d1的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量

public static void shellSort(int[] arr){
	if(arr == null || arr.length <= 1) return; 
	int gap=arr.length/2;
	while(gap>0){
		for(int i=1;i<arr.length ;i++){
			int temp=arr[i];
			int p=i;
			while(p>=gap&&arr[p-gap]>temp){
				arr[p]=arr[p-gap];
				p-=gap;
			}
			arr[p]=temp;
		}
		gap/=2;
	}
}

特征分析：
不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度与增量序列的选取有关，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(

选择排序

public static void simpleSelectSort(int[] arr){
	if(arr==null||arr.length<=1)
		return;
	for(int i=0;i<arr.length;i++){
		int start=i,minIndex=i;
		for(int j=i+1;j<arr.length;j++){
			if(arr[j]<arr[minIndex])
				minIndex=j;
		}
		int temp=arr[start];arr[start]=arr[minIndex];arr[minIndex]=temp;
	}
}

	public static void bubbleSort(int[] arr){
	    for(int end=arr.length-1;end>0;end--){
	        boolean changed=false;
	        for(int index=0;index<end;index++){
	            if(arr[index]>arr[index+1]){
	                int t=arr[index+1];
	                arr[index+1]=arr[index];
	                arr[index]=t;
	                changed=true;
	            }
	        }
	        if(changed==false) return;
	    }
	}

特征分析：

	public static void merge(int[] arr,int start1,int start2,int end2,int[] temp){
	    int end1=start2-1,index=0;
	    int p=start1,q=start2;
	    while(p<=end1||q<=end2){
	        if(q>end2||(p<=end1&&arr[p]<arr[q])){
	            temp[index++]=arr[p++];
	        }else{
	            temp[index++]=arr[q++];
	        }  
	    }
	    for(int i=0;i<index;i++){
	        arr[start1+i]=temp[i];
	    }
	}
    public static void mergeSort(int[] arr,int start,int end,int[] temp){
        if(start>=end) return;
        int mid=start+(end-start)/2;
        mergeSort(arr,start,mid,temp);
        mergeSort(arr,mid+1,end,temp);
        merge(arr,start,mid+1,end,temp);
    } 

public static void mergeSort(int[] arr,int[] temp){
        int size=1,low,mid,high,n=arr.length;  
        while(size<=n-1)  
        {  
            low=0;  
            while(low+size<=n-1)  
            {  
                mid=low+size-1;  
                high=mid+size;  
                if(high>n-1)//第二个序列个数不足size   
                    high=n-1;         
                merge(arr,low,mid+1,high,temp);//调用归并子函数 
                System.out.println("low:"+low+" mid:"+mid+" high:"+high); 
                low=high+1;//下一次归并时第一关序列的下界   
            }  
            size*=2;//范围扩大一倍   
        }  
    } 

    // d为数据长度
    private static void radixSorting(int[] arr, int d) {  
        for (int i = 1; i <=d; i++) {
            int[] res = countingSort(arr, i); // 依次对各位数字排序（直接用计数排序的变体）
            for(int j=0;j<arr.length;j++){
                arr[j]=res[j];
            } 
        } 
    } 
    // 利用计数排序对元素的每一位进行排序
    private static int[] countingSort(int[] arr, int expIndex) {
        int k = 9;
        int[] b = new int[arr.length];
        int[] c = new int[k + 1]; // 这里比较特殊：数的每一位最大数为9
        for (int i = 0; i < k; i++) {
            c[i] = 0;
        }
        for (int i = 0; i < arr.length; i++) {
            int d = getBitData(arr[i], expIndex);
            c[d]++;
        }
        for (int i = 1; i <= k; i++) {
            c[i] += c[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            int d = getBitData(arr[i], expIndex);
            b[c[d] - 1] = arr[i];// C[d]-1 就代表小于等于元素d的元素个数，就是d在B的位置
            c[d]--;
        }
        return b;
    }
    // 获取data指定位的数
    private static int getBitData(int data, int expIndex) {
        while (data != 0 && expIndex > 0) {
            data /= 10;
            expIndex--;
        }
        return data % 10;
    }
 
	public static int[] countSort(int[] a){
	    int b[] = new int[a.length];
        int max = a[0],min = a[0];
        for(int i:a){
            if(i>max) max=i;
            if(i<min) min=i;
        }//这里k的大小是要排序的数组中，元素大小的极值差+1
        int k=max-min+1;
        int c[]=new int[k];
        for(int i=0;i<a.length;++i){
            c[a[i]-min]+=1;//优化过的地方，减小了数组c的大小
        }
        for(int i=1;i<c.length;++i){
            c[i]=c[i]+c[i-1];
        }
        for(int i=a.length-1;i>=0;--i){
            b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
        }
        return b;
	}

	//假如排序的数据范围为（0-100），学生成绩
    public static void bucketSort(int[] arr){
        List<List<Integer>> buckets=new ArrayList<List<Integer>>();
        buckets.add(new ArrayList<Integer>());//成绩0-59的桶
        buckets.add(new ArrayList<Integer>());//成绩60-69
        buckets.add(new ArrayList<Integer>());//成绩70-79
        buckets.add(new ArrayList<Integer>());//成绩80-100 
        for(int i:arr){
            if(i>=0&&i<=59)    buckets.get(0).add(i);
            if(i>=60&&i<=69)   buckets.get(1).add(i);
            if(i>=70&&i<=79)   buckets.get(2).add(i);
            if(i>=80&&i<=100)  buckets.get(3).add(i); 
        }
        for(List<Integer> bucket:buckets){
            Collections.sort(bucket);
        }
        int index=0;
        for(List<Integer> bucket:buckets){
            for(int i:bucket){
                arr[index++]=i;
            }
        }
    }

特征分析：
1、对于N个待排数据，M个桶，如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。
2、桶排序是稳定的（如果桶内数据的排序算法选择的不是稳定的，桶排序就变成不稳定的）。

public class Solution {
    public boolean isAnagram(String s, String t) {
    	if(s.length()!=t.length()) return false;
        char[] a=s.toCharArray();
        char[] b=t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        boolean res;
        for(int i=0;i<a.length;i++){
        	if(a[i]!=b[i]){
        		return false;
        	}
        }
        return true;
    }
}

public class Solution {
	public int partition(int[] nums,int value,int begin,int end){
		int p=begin,q=end;
		while(p<q){
			while(p<=end&&nums[p]==value)p++;
			while(q>=begin&&nums[q]>value)q--;
			if(p<q){
				int t=nums[p];nums[p]=nums[q];nums[q]=t;
			}
		}
		return p;
	}
    public void sortColors(int[] nums) {
        if(nums.length<=1) return;
        int nextBegin=partition(nums,0,0,nums.length-1);
        if(nextBegin<nums.length){
        	partition(nums,1,nextBegin,nums.length-1);
        }
    }
}

public class Solution {
    public ListNode insertionSortList(ListNode head) {
    	ListNode myHead=new ListNode(-1),p;
    	while(head!=null){
    		p=head;
    		head=head.next;
    		insertElement(myHead,p);
    	}
    	return myHead.next;
    }
    private void insertElement(ListNode myHead,ListNode p){
    	ListNode pre=myHead,post=myHead.next;
    	while(post!=null&&post.val<=p.val){
    		pre=post;
    		post=post.next;
    	}
    	p.next=post;
    	pre.next=p;
    }
}

    public static ListNode sortList(ListNode head) {
    	int length=0;
    	ListNode p=head;
    	while(p!=null){
    		length++;
    		p=p.next;
    	}
    	if(length<=1) return head; 
    	ListNode myHead=new ListNode(-1);
    	myHead.next=head;
		mergerSort(myHead,length);
        return myHead.next;
    }
    private static void mergerSort(ListNode myHead,int length){
    	ListNode pre,start,end;
    	int size=1;
    	while(size<length){ 
    		pre=myHead;
    		while(pre.next!=null){
    			start=pre.next;
    			pre.next=merge(start,size);
    			int count=size*2;
    			while(count>0&&pre!=null){
    				pre=pre.next;
    				count--;
    			}
    			if(count>0||pre==null||pre.next==null) break;
    		}
    		size*=2;
    	}
    }
    private static ListNode merge(ListNode start,int size){
    	ListNode myHead=new ListNode(-1),end=myHead,second,last;
    	int count=size;
    	second=start;
    	while(count>0&&second!=null){
    		second=second.next;
    		count--;
    	} 
    	if(count>0) return start;//长度不够一个size
    	count=size;
    	last=second;
    	while(count>0&&last!=null){
    		last=last.next;
    		count--;
    	} 
    	ListNode p=start,q=second,t;
    	while(p!=second||q!=last){
    		if(q==last||(p!=second&&p.val<=q.val)){
    			
    			t=p; 
    			p=p.next;
    			t.next=null;
    			end.next=t;
    			end=end.next; 
    		}else{
    			t=q; 
    			q=q.next;
    			t.next=null;
    			end.next=t;
    			end=end.next;
    		}
    	}
    	end.next=last;
		return myHead.next; 
    }

public class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) return "";
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = nums[i]+"";
        }
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String i, String j) {
                String s1 = i+j;
                String s2 = j+i;
                return s2.compareTo(s1);
            }
        });
        //降序,直接比较i+j和j+i，就可以判断哪个应该放在前面
        if (strs[0].charAt(0) == '0') return "0";//最大为0,结果必为0
        StringBuilder res = new StringBuilder();
        for (String s:strs) {
            res.append(s);
        }
        return res.toString();
    }
}