排序算法是一種將元素集合按特定順序排列的算法。

例如：

您想將數(shù)字列表按升序排序或?qū)⒚Q列表按字典順序排序。

關(guān)于排序算法的實現(xiàn)、數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度和算法面試，有很多關(guān)于排序算法的問題。在進行算法面試之前，了解所有排序算法的優(yōu)缺點是非常重要的。

1.插入排序

思想：第一個為一個有序數(shù)組，之后每一個都向該數(shù)組中插入，從后往前，大于待插入數(shù)字的后移。

復(fù)雜度：插入排序是穩(wěn)定的。時間復(fù)雜度O(N^2),空間負責(zé)度O(1);

public static void  sort(int[] x)
	{
		int n = x.length;
		for( int i=1; i<n; i++)
		{
			//待插入元素
			int tmp = x[i];
			int j;
			for(j=i-1; j>=0 && x[j]>tmp; j--)
				x[j+1] = x[j];
			x[j+1] = tmp;
		}

2.選擇排序

思想：第一次選擇一個最小的跟第一個元素交換，第二次選擇剩下里面的最小的跟第二個交換，直到都比完。

復(fù)雜度：O(N^2),O(1)

public static void  sort(int[] x)
	{
		//選擇排序
		int n = x.length;
		for(int i=0; i<n; i++)
		{
			int min = i;//最小的
			for(int j=i+1; j<n; j++) 
				if(x[min]>x[j])
					min = j;//下標最小的
			int tmp = x[i];
			x[i] = x[min];
			x[min] = tmp;			
		}
	}

3.堆排序

初始時，把要排序的數(shù)的序列看作是一顆順序存儲的二叉樹，調(diào)整它們的順序，使之成為一個大根堆，此時根節(jié)點的值最大，把根節(jié)點和最后一個元素交換，把前面n-1個數(shù)又重排，重復(fù)第一次的操作。直到最后剩下兩個，交換它們的順序就得到了有序數(shù)組。

時間復(fù)雜度O(nlogn)

這個過程分為兩部分。一個是建堆，一個是堆頂與最后一個元素交換。

//堆排序
	public static void maxHeap(int[] a, int start, int end)//start是開始的父親，end是最后一個要排序的元素
	{
		//我們建的是大根堆，每次跟左右孩子里面最大的一個交換
		int left = start*2+1;
		int right = left+1;
		int tmp = a[start];
		int cur = start;
		for(; left<=end; cur=left, left=cur*2+1, right=left+1)//左節(jié)點為上一次循環(huán)中用來交換的位置，所以本次循環(huán)中將檢查left為父親的節(jié)點樹是否符合大根堆
		{
			if(left<end && a[left]<a[right])
				left++;
			if(tmp>=a[left])//tmp是需要調(diào)整的數(shù)，
				break;
			else //tmp<a[left],要換位置。tmp實際上就是a[cur]的位置
			{
				a[cur] = a[left];
				a[left] = tmp;
			}
		}
	}	
	public static void sort(int a[],int end)
	{
		int tmp;
		for(int i=end/2-1; i>=0; i--)
			maxHeap(a, i, end-1);//初始化大根堆		
		for(int i=end-1; i>=1; i--)
		{
			//交換根節(jié)點與最后一個節(jié)點
			tmp = a[0];
			a[0] = a[i];
			a[i] = tmp;
			maxHeap(a, 0, i-1);
		}
	}

4.交換排序之--冒泡排序

每次都把最大的冒泡到最后面。可以加個判斷，如果一趟中沒有交換，說明該數(shù)組已經(jīng)有序，就不需要再繼續(xù)掃描了。

public static void Sort(int[] x)
	{
		if(x.length==0) 
			System.exit(0);
		int n = x.length,max=0;
		for(int i=0; i<n; i++)
		{ 
			for(int j=0; j<n; j++) 
				if(x[i]<x[j])
				{
					int tmp = x[j];
					x[j] = x[i];
					x[i] = tmp;
				}
		}
	}

public static void Sort(int[] x)
	{
		if(x.length==0) 
			System.exit(0);
		boolean a=false;
		int n = x.length,max=0;
		for(int i=0; i<n; i++)
		{ 
			for(int j=0; j<n; j++) 
				if(x[i]<x[j])
				{
					int tmp = x[j];
					x[j] = x[i];
					x[i] = tmp;
					a = true;
				}
			if(!true)
				System.exit(0);
		}
	}

5.交換排序之--快速排序

借用圖：選擇一個基準(第一個或最后一個)每次比較之后判斷放在基準的哪一邊。

快速排序是不穩(wěn)定的。復(fù)雜度O(nlog2n)

    public static void quickSort(int[] nums, int left, int right){
        if(left>=right)
            return;
        int i=left, j=right;
        int temp = nums[left];
        while(i<j) {
            while(i<j && nums[j]>=temp)//必須是>=，否則相等的時候不會移動，會卡在這里
                j--;
            nums[i] = nums[j];
            while(i<j && nums[i]<=temp)
                i++;
            nums[j] = nums[i];
        }
        nums[i] = temp;
        System.out.println(Arrays.toString(nums));
        quickSort(nums, left,i-1);
        quickSort(nums,i+1,right);//i+1，不能是i，中間不能排
    }

6.歸并排序

把兩個或者兩個以上元素排好序，再把兩個有序段排序，以此類推，直到排完。

	//歸并排序
	public static void Sort(int a[], int begin, int end)
	{
		int mid = (begin+end)/2;
		if(begin<end)//少了這句會堆棧溢出
		{
			Sort(a, begin, mid);
			Sort(a, mid+1, end);
			Merge(a, begin, mid, end);
		}		
	}
	public static void Merge(int a[], int begin, int mid, int end)
	{ 
		int tmp[] = new int[end-begin+1];//新的數(shù)組
		int l = begin, r = mid+1;//左右指針
		int k = 0;//新數(shù)組的指針
		while(l<=mid && r<=end)
		{
			if(a[l] > a[r])
				tmp[k++] = a[r++];
			else
				tmp[k++] = a[l++]; 
		}
		while(l<=mid) 
			tmp[k++] = a[l++]; 		
		while(r<=end)
			tmp[k++] = a[r++]; 
		//把已合并的列入原數(shù)組
		for(int i=0; i<end-begin+1; i++)
			a[begin+i] = tmp[i];		
	}

7.基數(shù)排序