多种排序总结

闲来无事，复习下算法，对各种经典的排序算法进行初步的总结。巩固下基础，同时为将来找工作做下准备，也作为我博客正式发文的开端。

所有排序默认从小到大。时间复杂度详见总结。

一、选择排序（Selectionsort)

选择排序（Selectionsort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。例如a[] = {112,123,12,23,234,345,435,345,21,2};第一个循环只能将最小的数字2放到第一位，然后第二次循环，12放到第二位。

void selectSort(int *a,int n) 
{ 
     int i,j,k,temp; 
     for(i=0;i<n-1;i++)
    { 
        k=i; /*给记号赋值*/ 
        for(j=i+1;j<n;j++) 
            if(a[k]>a[j])
				k=j; /*是k总是指向最小元素*/ 
        if(i!=k)
        { 
            /*当k!=i是才交换，否则a[i]即为最小*/     
            temp=a[i]; 
            a[i]=a[k]; 
            a[k]=temp;
         } 
     } 
}

package top.fangheart.Algorithm.sort;
/**
 * Created by FangHeart on 2016/8/29.
 */
public class SelectSort {
    int a[] = {112,123,12,23,234,345,435,345,21,2};
    int i,j,k,t;
    public void sort(){
        System.out.println("初始数组为:");
        for (int l = 0; l < 10; l++) {
            System.out.print(a[l]+ " ");
        }
        System.out.print("\n");
        for (int i = 0; i < 9; i++) {
            k = i;
            for (int j = i+1; j < 10; j++) {
                if (a[j]<a[k])
                    k =j;
                if (i!=k){
                    t = a[i];
                    a[i] = a[k];
                    a[k] = t;
                }
            }
            System.out.print("第"+i+"次排序后:");
            for (int l = 0; l < 10; l++) {
                System.out.print(a[l]+ " ");
            }
            System.out.print("\n");
        }
    }
}

二、冒泡排序（Bubble Sort）

冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

void bubbleSort(){
	int i,j,t;
	int a[6] = {71,5,7,10,6,2};
	
	
	for(i = 0; i < 6 - 1;i++){
		for(j = 0; j < 6 - 1 - i; j++){
			if(a[j] > a[j+1]){
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
	printf("冒泡排序后:");
	for(i = 0 ; i < 6; i++){
		printf("%d ",a[i]);
	}
}

public void  sort(){
        int a[] = {123,124,454356,132,1234,2354};
        int temp;
        int n = a.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-1-i; j++) {
                if(a[j] > a[j+1]){
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        System.out.println("排序后:");
        for (int i = 0; i < n; i++) {
            System.out.printf(a[i] + " ");
        }
    }

三、插入排序(InsertSort)

插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果被扫描的元素（已排序）大于新元素，将该元素后移一位
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

具体过程如下图所示：

void insertSort(int a[],int n){
	int i=0,j;
	int temp;
	for (i=1;i<n;i++)
	{
		temp = a[i];
		j = i - 1;
		while (j>=0&&temp<a[j])
		{
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = temp;
	}
}

int a[]={2,1,7,8,4,6,5,9,3,0};
    int i,j;
    int temp;
    public void sort(){
        for(i=1;i<a.length;i++){
            temp=a[i];
            j = i-1;
            while(j>=0&&temp<a[j]){
                a[j+1] = a[j];
                j--;
            }
            a[j+1]=temp;
        }
        for(int m=0;m<a.length;m++){
            System.out.print(a[m]+" ");
        }
    }

四、简单桶排序(BucketSort)

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。

void bucketSort()
{
	int n,book[1000],i,j,t;
	 
	for (i = 0; i <= 1000; i++){
		book[i] = 0;
	}
	
	printf("请输入排序个数n:");
	scanf("%d", &n);
	
		printf("请输入数字(排序数字需要小于1000):");
		for (i = 0 ; i < n; i++){
			scanf("%d ",&t);
			book[t]++;
		}
		
		for(i = 0; i <= 1000; i++){
			for(j = 0; j < book[i]; j++)
				printf("%d",i);
		}
		 
}

public void sort(){
        int n;
        int book[] = new int[1000];
        for(int i = 0; i < 1000; i++){
            book[i] = 0;
        }
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入排序的个数n:");
        n = scanner.nextInt();
        System.out.println("请输入小于1000的" + n + "个数:");
        for(int i = 0; i < n; i++){
            int t =scanner.nextInt();
            book[t]++;
        }
        System.out.println("经过排序后");
        for(int i = 0; i < 1000; i++)
            for(int j = 0; j < book[i]; j++)
            {
                System.out.println(i + " ");
            }
    }

五、快速排序(QuickSort)

快速排序通常明显比同为Ο(nlogn)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。

步骤：

1.从数列中挑出一个元素作为基准数（一般为第一个数）。
2.分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。（注意这个过程先从右到左比较，再从左到右）
3.再对左右区间递归执行第二步，直至各区间只有一个数。

void quickSort(int a[],int left,int right){
	int i,j,t,temp;
	if(left > right)
		return;
	temp = a[left];
	i = left;
	j = right;
	
	
	while(i!=j){
		while(a[j]>=temp && i <j){
			j--;
		}
		while(a[i]<=temp && i <j){
			i++;
		}
		
		if(i<j){
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	 a[left] = a[i];
	 a[i] = temp;
	 
	 quickSort(a,left,i-1);
	 quickSort(a,i+1,right);
		
}

public int a[] = {456,124,454356,132,1234,2354};
    public void sort(int left,int right){
        int i,j,t,temp;
        i = left;
        j = right;
        if (left > right)
            return;
        temp = a[left];
        while (i != j){
            while (a[j]>=temp && i<j){
                j--;
            }
            while (a[i]<=temp && i<j){
                i++;
            }
            if (i < j){
                t = a[i];
                a[i] = a[j];
                a[j] =t;
            }
        }
        a[left] = a[i];
        a[i] = temp;
        sort(left,i-1);
        sort(i+1,right);
    }
    public void print(){
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k] + " ");
        }
    }

六、堆排序(HeapSort)

堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根结点的值小于（或大于）两个子节点的值，同时，根节点的两个子树也分别是一个堆。

堆排序就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。
堆排序的实现需要解决的两个关键问题：
（1）将一个无序序列构成一个堆。
（2）输出堆顶元素后，调整剩余元素成为一个新堆。

public class HeapSort {
    /**
     * 构建大顶堆
     */
    public static void adjustHeap(int[] a, int i, int len) {
        int temp, j;
        temp = a[i];
        for (j = 2 * i; j < len; j *= 2) {// 沿关键字较大的孩子结点向下筛选
            if (j < len && a[j] < a[j + 1])
                ++j; // j为关键字中较大记录的下标
            if (temp >= a[j])
                break;
            a[i] = a[j];
            i = j;
        }
        a[i] = temp;
    }
    public static void heapSort(int[] a) {
        int i;
        for (i = a.length / 2 - 1; i >= 0; i--) {// 构建一个大顶堆
            adjustHeap(a, i, a.length - 1);
        }
        for (i = a.length - 1; i >= 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            adjustHeap(a, 0, i - 1);// 将a中前i-1个记录重新调整为大顶堆
        }
    }
    public static void main(String[] args) {
        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}

七、希尔排序(ShellSort)

希尔排序也成为“缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序。因此，我们要采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。希尔排序是对直接插入排序算法的优化和升级。

所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，例如｛2,1,3,6,4,7,5,8,9｝就可以称为基本有序了。但像｛1,5,9,3,7,8,2,4,6｝这样，9在第三位，2在倒数第三位就谈不上基本有序。

public static void shellSortSmallToBig(int[] data) {
      int j = 0;
      int temp = 0;
      for (int increment = data.length / 2; increment > 0; increment /= 2) {
          System.out.println("increment:" + increment);
          for (int i = increment; i < data.length; i++) {
              // System.out.println("i:" + i);
              temp = data[i];
              for (j = i - increment; j >= 0; j -= increment) {
                  // System.out.println("j:" + j);
                  // System.out.println("temp:" + temp);
                  // System.out.println("data[" + j + "]:" + data[j]);
                  if (temp < data[j]) {
                      data[j + increment] = data[j];
                  } else {
                      break;
                  }
              }
              data[j + increment] = temp;
          }
          for (int i = 0; i < data.length; i++)
              System.out.print(data[i] + " ");
      }
  }
  public static void main(String[] args) {
      int[] data = new int[] { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };
      shellSortSmallToBig(data);
      System.out.println(Arrays.toString(data));
  }

八、归并排序(MergeSort)

归并排序是利用递归与分治技术将数据序列化分成越来越小的半子表，再对班子表排序，最后再用递归方法将排序好的半子表合并成越来越大的有序列表。
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 public class MergeSort {  
	/** 
	 * 归并排序 
	 * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 
	 * 时间复杂度为O(nlogn) 
	 * 稳定排序方式 
	 * @param nums 待排序数组 
	 * @return 输出有序数组 
	 */  
	public static int[] sort(int[] nums, int low, int high) {  
		int mid = (low + high) / 2;  
		if (low < high) {  
			// 左边  
			sort(nums, low, mid);  
			// 右边  
			sort(nums, mid + 1, high);  
			// 左右归并  
			merge(nums, low, mid, high);  
		}  
		return nums;  
	}  
  
	public static void merge(int[] nums, int low, int mid, int high) {  
		int[] temp = new int[high - low + 1];  
		int i = low;// 左指针  
		int j = mid + 1;// 右指针  
		int k = 0;  
  
		// 把较小的数先移到新数组中  
		while (i <= mid && j <= high) {  
			if (nums[i] < nums[j]) {  
				temp[k++] = nums[i++];  
			} else {  
				temp[k++] = nums[j++];  
			}  
		}  
  
		// 把左边剩余的数移入数组  
		while (i <= mid) {  
			temp[k++] = nums[i++];  
		}  
  
		// 把右边边剩余的数移入数组  
		while (j <= high) {  
			temp[k++] = nums[j++];  
		}  
  
		// 把新数组中的数覆盖nums数组  
		for (int k2 = 0; k2 < temp.length; k2++) {  
			nums[k2 + low] = temp[k2];  
		}  
	}  
  
	  
	// 归并排序的实现  
	public static void main(String[] args) {  
  
		int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };  
  
		MergeSort.sort(nums, 0, nums.length-1);  
		System.out.println(Arrays.toString(nums));  
	}  
}