Contents

1. 1. 排序类型总结
   1. 1.1. （1）插入排序
   2. 1.2. （2）冒泡排序
   3. 1.3. (3)快速排序
   4. 1.4. (4)选择排序
   5. 1.5. (5)归并排序

排序类型总结

排序方式	平均复杂度	最坏情况	最好情况	空间复杂度(额外需要空间）	稳定性	复杂性
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
快速排序	O(nlog_{2}n)	O(n^2)	O(n)	O(log_{2}n)	不稳定	较复杂
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	简单
堆排序	O(nlog_{2}n)	O(nlog_{2}n)	O(nlog_{2}n)	O(1)	不稳定	较复杂
归并排序	O(nlog_{2}n)	O(nlog_{2}n)	O(nlog_{2}n)	O(n)	稳定	较复杂
希尔排序	O(n^{1.3})			O(1)	不稳定	较复杂
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定	较复杂

（1）插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

如果比较的操作代价比交换大的话，可以用二分查找来查找插入点。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

JAVA实现

1. 传统排序算法

   public static void insertion_sort( int[] arr ){
       for( int i=0; i<arr.length-1; i++ ) {	
           for( int j=i+1; j>0; j-- ) {
               if( arr[j-1] <= arr[j] )
                   break;
               int temp = arr[j];
               arr[j] = arr[j-1];
               arr[j-1] = temp;
           }
       }
   }

2. 二分法排序

   public static int searchInsert(int start, int end, int[] nums, int target)
   {
       if( target <= nums[0]){
           return 0;
       }
       if(target > nums[end])
           return end+1;
       if(target == nums[end])
           return end;
       if(start == end || ((end-start)==1 && target>nums[start] && target<nums[end]))
           return start+1;
       int mid = start + (end-start)/2;
       if(target > nums[mid]){
           return searchInsert(mid, end, nums, target);
       }else if(target < nums[mid]){
           return searchInsert(start,mid,nums,target);
       }else if(target == nums[mid]){
           return mid;
       }
       return -1;
   }
   
   public static void insertion_sort(int[] arr)
   {
       int index,temp;
       for( int i=1; i<arr.length; i++ ) {
           index = searchInsert(0, i-1, arr, arr[i]);
           
           System.out.println("index:"+index);
   
           for(int j = i;j>index;j--){
               temp = arr[j];
               arr[j] = arr[j-1];
               arr[j-1] = temp;
           }
           for (int anArr : arr) {
               System.out.println(anArr);
           }
       }
   }

（2）冒泡排序

冒泡排序（英语：Bubble Sor）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

代码实现：

public static void bubbleSort(int[] arr) {
    int i, temp, len = arr.length;
    boolean changed;
    do {
      changed = false;
      for (i = 0; i < len - 1; i++) {
        if (arr[i] > arr[i + 1]) {
          temp = arr[i];
          arr[i] = arr[i + 1];
          arr[i + 1] = temp;
          changed = true;
        }
      }
    } while (changed);
  }

(3)快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n个项目要O(n\log n) 次比较。在最坏状况下则需要 O(n^{2})次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 O(n\log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

步骤为：

1. 从数列中挑出一个元素，称为”基准”（pivot），可以直接挑选最后一个数
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4. 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

public static void sort(int[] array, int left,int right) {
    if (left > right) {
			return;
		}
		int storeIndex = partition(array, left, right);
		sort(array, left, storeIndex - 1);
		sort(array, storeIndex + 1, right);
	}
	sort(array, 0, array.length - 1);
}

public static void swap(int[] array, int i, int k) {
	int temp = array[i];
	array[i] = array[k];
	array[k] = temp;
}
	
// 数组分区，左小右大
public static int partition(int[] array, int left, int right) {
	int storeIndex = left;        
	int pivot = array[right]; // 直接选最右边的元素为基准元素
	for (int i = left; i < right; i++) {
		if (array[i] < pivot) {
			swap(array, storeIndex, i);
			storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
		}
	}
	swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
	return storeIndex;
}

public static quickSort(int[] arry)}{
    sort(arry, 0, array.length-1);
}

(4)选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public static void selection_sort(int[] arr) {
	int i, j, min, temp, len = arr.length;
	for (i = 0; i < len - 1; i++) {
		min = i;//未排序序列中最小数据数组下标
		for (j = i + 1; j < len; j++)//在未排序元素中继续寻找最小元素，并保存其下标
			if (arr[min] > arr[j]){
				min = j;}
		temp = arr[min]; //将最小元素放到已排序序列的末尾
		arr[min] = arr[i];
		arr[i] = temp;
	}
}

(5)归并排序

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)。

排序算法步骤如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
	if (start >= end)
		return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort_recursive(arr, result, start1, end1); //
	merge_sort_recursive(arr, result, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		result[k++] = arr[start1++];
	while (start2 <= end2)
		result[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
	int len = arr.length;
	int[] result = new int[len];
	merge_sort_recursive(arr, result, 0, len - 1);
}