导读:

最近看了一些有关排序算法的东西，这里就是简单的记录一下。
主要是 ：（默认实现的 升序）
选择排序、插入排序、冒泡排序、快速排序、归并排序、堆排序。

选择排序

• 时间复杂度：O(n²)。
• 空间复杂度：O(1)。
• 主要思想： 就是2遍循环遍历数组，外层循环控制每个数字应该放的数字，内层循环找到这个数组的最小值，把它放到应该放到的位置（即外层循环控制的位置）上去。
• 代码： 注意在写代码时用数组的下标来找数组的相应的最小值，不要直接用值比较
  　　，这样在后面要交换的时候 是 没有对数组的内部元素进行操作的。

	public static void selectionSort(int[] arr) {
   
		if(arr == null || arr.length < 1) {
   
			return ;
		}
		
		for(int i = 0; i < arr.length; i++) {
   
			int minIndex = i;	// 要用下标来找，不能用数值来找，否则后面交换的时候不是在数组内交换的（总之就是交换不过来）
			for(int j = i; j < arr.length; j++) {
   
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
		
	}
	
	// 对arr[a], arr[b] 这两个数进行交换
	public static void swap(int[] arr, int a, int b) {
   
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

• 稳定性：不能做到稳定性。
  比如数组 ： 2，3，2，6，6，6，1，2
  这样排完了之后1在最前面，可是这些2的相对顺序也已经改变了。

插入排序

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 主要思想： 可以想象打扑克牌时理牌的情形。
  也是遍历2遍，一开始认为第一个数是排好的了，外层循环从1位置开始遍历，内存循环从外层循环的位置一直往前找，有顺序不符的就交换。

	public static void insertionSort(int[] arr) {
   
		if(arr == null || arr.length < 1) {
   
			return ;
		}
		
		for(int end = 1; end < arr.length; end++) {
   		//[0...end-1]是已经排好的范围
			for(int j = end; j > 0 && arr[j] < arr[j-1]; j--) {
      //j不能到0，到0的话，下面的j-1会越界
				swap(arr, j, j-1);
			}
		}
		
	}
	
	// 对arr[a], arr[b] 这两个数进行交换
	public static void swap(int[] arr, int a, int b) {
   
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

• 稳定性： 可以做到稳定性。 就是在往前找的时候，如果遇到相等的数就不动、不交换就可以了，这样他们的相对顺序还是原来的那样。

冒泡排序

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 主要思想：2个2个的数依次比较，大的数放在后面，这样完了后也就是有序的数组了。 因为整个过程很像 冒泡的过程，大的数都浮到了最后面。
• 代码：

	public static void bubbleSort(int[] arr) {
   
		if(arr == null || arr.length < 1) {
   
			return ;
		}
		
		for(int end = arr.length-1; end >= 0; end--) {
   
			
			for(int start = 0; start < end; start++) {
   
				if(arr[start] > arr[start+1]) {
   
					swap(arr, start, start+1);
				}
			}
			
		}
		
	}
	
	// 对arr[a], arr[b] 这两个数进行交换
	public static void swap(int[] arr, int a, int b) {
   
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

• 稳定性： 可以做到稳定性。 就是2个数在比较的时候，如果是相等的话不交换就好。

快速排序

• 时间复杂度：O(N*logN)
• 空间复杂度：O( logN ) 就是partition的过程，在找中点的时候用了一定的空间存储
• 主要思想：1. 先在数组中随机找一个数字（把这个数字放在数组的最右边或者最左边，最后再交换一下），再根据这个数组在数组中划分，小于的放一边，等于的放一边，大于的放一边。之后再对小于的、大于的部分递归调用这个过程，整个数组就是有序的了。 （这是最优化后的做法了）

2. 但是在找这个数字的时候是随机找的，可以选用第一个数字或者最后一个数字。但是、but、however，这样的话，对于本来就是几乎有序的数组 来说，时间复杂度会退化到O(n²)。
3. 还有一种是把小于等于的放一变，大于的放一边（或者小于的放一边，大于等于的放一边）。但是、but、however，这样的话，对于本来就有很多重复元素的数组来说，时间复杂度也会退化成O(n²)。因为这样每次划分只搞定了一个数字。

• 代码

	public static void quickSortMain(int[] arr) {
   
		if(arr == null || arr.length < 1) {
   
			return ;
		}
		quickSort(arr, 0, arr.length-1);
	}
	
	public static void quickSort(int[] arr, int left, int right) {
   
		if(left >= right) {
   
			return ;
		}
		
				 //记得这里有一个left的偏移.... 要保证在left到right的区间里...
		swap(arr, left+(int)(Math.random()*(right-left+1)) , right);
		int[] p = partition(arr, left, right);	//partition返回的数组里只有2个数。
		quickSort(arr, left, p[0]-1);
		quickSort(arr, p[1]+1, right);
		
	}
	
	// 返回的第一个数是 等于部分的左闭区间， 第二个数是 等于部分的右闭区间
	public static int[] partition(int[] arr, int left, int right) {
   
		int less = left-1;
		int more = right;
		int index = left;
		
		while(index < more) {
   
			if(arr[index] < arr[right] ) {
   
				swap(arr, index++, ++less);
				
			} else if(arr[index] > arr[right]) {
   
				swap(arr, index, --more);
				
			} else {
   	// arr[index] == arr[right]
				index++;
			} 
		}
		swap(arr, right, more);
		
		return new int[] {
   less+1, more};
	}
	
	// 对arr[a], arr[b] 这两个数进行交换
	public static void swap(int[] arr, int a, int b) {
   
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

• 稳定性： 一般来说不能做到稳定性。 但是严格来讲是可以做到的，有兴趣的可以去搜索有关“01 stable sort”的资料。

归并排序

• 时间复杂度：O(N*logN)
• 空间复杂度：O(N) 要开辟辅助数组
• 主要思想：将数组二分二分的一直分下去，直到只剩1个数字的时候，认为他是排好的（只有1个数字，没有其他数字相比较，当然是排好的了），然后在从分的时候，2组2组的往上合并，在合并的过程中，先放2部分中最小的那个，把放的数字装到开辟的辅助数组中，然后再将这个辅助数组 放到 原数组中他对应应该在的位置。这样一直放上去后，直到整个数组都分完合完后，也就是整个数组有序的时候。
  这样的做法是二分归并。 还有K分归并，就是有K个数组，把这K个数组合并成一个有序数组。主要就是用分治的思想，也就是先2个2个合并（不交叉的2项：比如就是1和2合并，3和4合并。不是1和2合并成整体再和3合并，进而再和4合并，这样就很慢…）。
• 代码

	public static void mergeSortMain(int[] arr) {
   
		if(arr == null || arr.length < 1) {
   
			return;
		}
		mergeSort(arr, 0, arr.length-1);
	}
	
	public static void mergeSort(int[] arr, int left, int right) {
   
		if(left >= right) {
   
			return ;
		}
		
		int mid = left + (right-left)/2 ;
		mergeSort(arr, left, mid);
		mergeSort(arr, mid+1, right);
		merge(arr, left, mid, right);
	}
	
	public static void merge(int[] arr, int left, int mid, int right) {
   
		int[] help = new int[right-left+1];
		int index = 0;
		int i = left;
		int j = mid+1;
		
		while(i <= mid && j <= right) {
   
			help[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
		}
		while(i <= mid) {
   
			help[index++] = arr[i++];
		}
		while(j <= right) {
   
			help[index++] = arr[j++];
		}
		
		for(int k = 0; k < help.length; k++) {
   
			arr[left+k] = help[k];
		} 
	}

• 稳定性 ： 可以做到稳定性，就是在合并的过程中，如果遇到相等的，就先放最前面的那个数字就可以了。
  有个小拓展：空间复杂度可以达到O(1)，但是很难，有兴趣的可以去搜索“归并排序，内部缓存法”资料。
• 小应用：小和问题 和 逆序对问题。

堆排序

• 时间复杂度：O(N*logN)
• 空间复杂度：O(1)
• 主要思想： 就是把数组建立成一个堆（大根堆或小根堆都可以），然后在依次取出堆顶元素的顺序就是 排好序 的数组元素顺序了。 如果只是一个建堆的过程，那么时间复杂度只是O(N)。
  对于堆和数组来说，其下标关系：
  左孩子是 （index2+1）。右孩子是（index2+2）。
  父亲节点是（index-1）/ 2。
• 代码

	public static void heapSort(int[] arr) {
   
		if(arr == null || arr.length < 1) {
   
			return;
		}
		
		for(int i = 0; i < arr.length; i++) {
   
			heapInsert(arr, i);
		}
		
		int size = arr.length;		// 用size来维护这个堆的大小，从而在数组中实现排序
		swap(arr, 0, --size);
		while(size > 0) {
   
			heapify(arr, 0, size);
			swap(arr, 0, --size);
		}
		
	}
	
	// 将arr[index] 的元素 放入堆中， 并使其还是一个堆 （shift_up操作）
	public static void heapInsert(int[] arr, int index ) {
   
		while( arr[(index-1)/2 ] < arr[index] )  {
   
			swap(arr, (index-1)/2, index);
			index = (index-1) / 2;
		} 
	}
	
	// 对堆中的位置为index的元素进行 shift_down操作， 使其满足一个大小为size的堆
	public static void heapify(int[] arr, int index, int size) {
   
		int left = index*2 + 1;
		while(left < size) {
   
			// largest 存储的是下标
			int largest = left+1 < size && arr[left+1] > arr[left] ? left+1 : left;	
			largest = arr[index] >= arr[largest] ? index : largest;
			if(largest == index) {
   
				break;
			}
			swap(arr, index, largest);
			index = largest;
			left = index*2 + 1;
		} 
	}
	
	// 对arr[a], arr[b] 这两个数进行交换
	public static void swap(int[] arr, int a, int b) {
   
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

• 稳定性： 做不到稳定性。
• 小应用： 在流动的数据中快速找到中位数，以及有关优先队列的各种问题。