几种排序算法的实现

引言

• 排序算法是重要的基础算法；
• 排序算法的效率至关重要；
• 任何算法的空间效率和时间效率不可兼得，所以没有最好的算法，只有最合适的算法；
• 本文总结了几种排序算法，并分析了他们的适用场景，使用的语言为java和js；

选择排序（selection sort）

• 思想：对于一个数组a，找出数组中的最小元素并和a[0]交换，然后忽略a[0]，再次找出数组中的最小元素并与a[1]交换，以此类推；
• java实现：

package algorithm;

public class SelectionSort {

	public static void main(String[] args) {
		int[] nums = { 1, 54, 6, 3, 78, 34, 12, 45 };
		sort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void sort(int[] myArray) {
		for (int i = 0; i < myArray.length; i++) {
			int temp = myArray[i];
			int position = i;
			for (int j = i + 1; j < myArray.length; j++) {
				if (myArray[j] < temp) {
					temp = myArray[j];
					position = j;
				}
			}
			myArray[position] = myArray[i];
			myArray[i] = temp;
		}
	}
}

• js实现：

var nums = [1, 54, 6, 3, 78, 34, 12, 45];
var selectionSort = function(nums){
	for(var i=0; i<nums.length; i++){
		var temp = nums[i];
		var position = i;
		for(var j=i; j<nums.length; j++){
			if(nums[j]<temp){
				temp = nums[j];
				position = j;
			}
		}
		nums[position] = nums[i];
		nums[i] = temp;
	}
}

selectionSort(nums);
for(var number in nums){
	console.log(nums[number]);
}

插入排序（Insertion sort）

• 思想：从数组的第二个元素开始，将数组中的每一个元素按照规则插入到已排好序的数组中以达到排序的目的；
• java排序：

package algorithm;

public class InsertionSort {

	public static void main(String[] args) {
		int[] nums = { 1, 54, 6, 3, 78, 34, 12, 45 };
		sort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void sort(int[] myArray) {
		int temp = 0;
		for (int i = 1; i < myArray.length; i++) {
			int j = i - 1;
			temp = myArray[i];
			for (; j >= 0 && temp < myArray[j]; j--) {
				myArray[j + 1] = myArray[j]; // 将大于temp的值整体后移一个单位
			}
			myArray[j + 1] = temp;
		}
	}
}

• js实现：

var nums = [3,4,1,7,2,9,10,0];
var insertionSort = function(nums){
	for(var i=1; i<nums.length; i++){
		var temp = nums[i];
		for(var j = i-1; j>=0&&nums[j]>temp; j--){
			nums[j+1] = nums[j];
		}
		nums[j+1]=temp;
	}
}

insertionSort(nums);
for(var number in nums){
	console.log(nums[number]);
}

希尔排序（shell sort）

• 希尔排序是改进后的插入排序；
• 思想：由于数组越接近有序，插入排序时间复杂度越低，所以希尔排序不是直接对数组进行插入排序，而是先对数组分成若干组，对每一组分别进行插入排序，使得数组变得”更加有序”之后再扩大每组的元素个数，再对每组进行插入排序，以此类推，直至元素全部有序，这是一种为了降低时间复杂度的”渐进式”的插入排序；
• java实现：

package algorithm;

public class InsertionSort {

	public static void main(String[] args) {
		int[] nums = { 1, 54, 6, 3, 78, 34, 12, 45 };
		sort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void sort(int[] myArray) {
		double d = myArray.length;
		while(true){
			d = Math.ceil(d/2);
			int inteval = (int)d;
			for(int i =0; i<inteval; i++){
				for(int j=i+inteval; j<myArray.length; j+=inteval){
					int temp = myArray[j];
					int k = j-inteval;
					for(; k>=0&&myArray[k]>temp;k-=inteval){
						myArray[k+inteval] = myArray[k];
					}
					myArray[k+inteval] = temp;
				}
			}
			
			if(inteval==1){
				break;
			}
		}
	}
}

• js实现：

var nums = [3,1,4,2,7,2,3,10];
var shellSort = function(nums){
	var d = nums.length;
	while(true){
		d = Math.ceil(d/2);

		for(var i=0; i<d; i++){
			for(var j=i+d; j<nums.length; j++){
				var temp = nums[j];
				for(var k = j-d; k>=0&&nums[k]>temp;k-=d){
					nums[k+d] = nums[k];
				}
				nums[k+d] = temp;
			}
		}
		if(d==1){
			break;
		}
	}
}

shellSort(nums);
for(var number in nums){
	console.log(nums[number]);
}

归并排序（Merge Sort）

• 归并排序是分治法在排序算法中的的典型实现；
• 归并排序是将一个数组分为两半A、B（或更多部分），对这两半分别排序后，再将他们归并为一个有序数组；
• 合并的方法：将A数组中的一个元素与B数组中的一个元素相比较，并将较小的元素复制到第三个新数组中，当其中一个数组到达末尾时，将另一个数组中剩余元素复制到第三个数组中即可；
• java实现：

package algorithm;

public class InsertionSort {

	public static void main(String[] args) {
		int[] nums = { 1, 54, 6, 3, 78, 34, 12, 45 };
		sort(nums,0,nums.length-1);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void sort(int[] myArray,int left,int right) {
		if(left<right){
			int center = (left+right)/2;
			sort(myArray,left,center);  //递归
			sort(myArray,center+1,right);
			merge(myArray,left,center,right);
		}
	}
	
	public static void merge(int[] myArray,int left,int center,int right){
		int[] result = new int[myArray.length];
		int mid = center+1;
		int third = left; //记录新的数组result的偏移量
		int tmp = left;
		//归并
		while(left<=center&&mid<=right){
			if(myArray[left]<=myArray[mid]){
				result[third++] = myArray[left++];
			}else{
				result[third++] = myArray[mid++];
			}
		}
		
		//处理归并剩余部分
		while(mid<=right){
			result[third++] = myArray[mid++];
		}
		
		while(left<=center){
			result[third++] = myArray[left++];
		}
		
		//复制回原数组
		while(tmp<=right){
			myArray[tmp] = result[tmp];
			tmp++;
		}
	}
}

• js实现：

var nums = [1, 54, 6, 3, 78, 34, 12, 45];
var mergeSort = function(nums,left,right){
	if(left<right){
		var center = Math.floor((left+right)/2);
		mergeSort(nums,left,center);
		mergeSort(nums,center+1,right);
		merge(nums,left,center,right);
	}
}

var merge = function(nums,left,center,right){
	var mid = center+1;
	var tmp = left;
	var third = left;
	var result = new Array(nums.length);

	while(left<=center&&mid<=right){
		if(nums[left]<nums[mid]){
			result[third++] = nums[left++];
		}else{
			result[third++] = nums[mid++];
		}
	}

	while(left<=center){
		result[third++] = nums[left++];
	}

	while(mid<=right){
		result[third++] = nums[mid++];
	}

	while(tmp<=right){
		nums[tmp] = result[tmp];
		tmp++;
	}
}

mergeSort(nums,0,nums.length-1);
for(var number in nums){
	console.log(nums[number]);
}

冒泡排序（Bubble sort）

• 从第一个元素开始，比较相邻的元素，如果第一个比第二个大，就交换他们两个；
• 依次往后，对每一对相邻元素作同样的工作，直到序列最后，最后的元素应该会是最大的数；
• 从第一个元素开始，重复上面两步，直到倒数第二个元素就停止（最后一个元素肯定是序列中最大的，不用再次比较）；
• 重复上面的过程，直到序列末尾；
• java实现：

package algorithm;

public class InsertionSort {

	public static void main(String[] args) {
		int[] nums = { 1, 54, 6, 3, 78, 34, 12, 45 };
		sort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void sort(int[] myArray) {
		int tmp;
		for(int i =0; i<myArray.length-1; i++){
			for(int j=0; j<myArray.length-1-i; j++){
				if(myArray[j]>myArray[j+1]){
					tmp = myArray[j];
					myArray[j] = myArray[j+1];
					myArray[j+1] = tmp;
				}
			}
		}
	}
}

• js实现：

var nums = [1,5,3,6,2,7,9];
var bubbleSort = function(nums){
	var temp;
	for(var i=0 ;i<nums.length-1; i++){
		for(var j=0; j<nums.length-1-i; j++){
			if(nums[j]>nums[j+1]){
				tmp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = tmp;
			}
		}
	}
}

bubbleSort(nums);
for(var number in nums){
	console.log(nums[number]);
}

快速排序(Quick Sort)

• 思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分；
• java实现：

package algorithm;

public class InsertionSort {

	public static void main(String[] args) {
		int[] nums = { 1, 54, 6, 3, 78, 34, 12, 45 };
		quickSort(nums,0,nums.length-1);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void quickSort(int[] list, int low, int high) {
		if (low < high) {
			int middle = getMiddle(list, low, high); // 将list数组进行一分为二
			quickSort(list, low, middle - 1); // 对低字表进行递归排序
			quickSort(list, middle + 1, high); // 对高字表进行递归排序
		}
	}

	public static int getMiddle(int[] list, int low, int high) {
		int tmp = list[low]; // 数组的第一个作为中轴
		while (low < high) {
			while (low < high && list[high] >= tmp) {
				high--;
			}

			list[low] = list[high]; // 比中轴小的记录移到低端
			
			while (low < high && list[low] <= tmp) {
				low++;
			}

			list[high] = list[low]; // 比中轴大的记录移到高端
		}
		list[low] = tmp; // 中轴记录到尾
		return low; // 返回中轴的位置
	}
}

• js实现：

var nums = [1, 54, 6, 3, 78, 34, 12, 45];
var quickSort = function(nums,low,high){
	if(low<high){
		var middle = sort(nums,low,high);
		quickSort(nums,low,middle-1);
		quickSort(nums,middle+1,high);
	}	
}

var sort = function(nums, low, high){
	var tmp = nums[low];
	while(low<high){
		while(low<high&&tmp<=nums[high]){
			high--;
		}
		nums[low] = nums[high];
		while(low<high&&tmp>=nums[low]){
			low++;
		}
		nums[high] = nums[low];
	}

	nums[low] = tmp;
	return low;
}

quickSort(nums,0,nums.length-1);
for(var number in nums){
	console.log(nums[number]);
}

堆排序(Heap Sort)

• 堆的基本概念：
  • 堆是节点含有可比较对象，并以如下方式组织的完全二叉树：
  • 每个节点含有的对象不小于(最大堆)/不大于(最小堆)其后代中的对象；
  • 最大（小）堆的根含有堆中最大（小）的对象；
  • 最大（小）堆中任何节点的子树也是最大（小）堆；
• 堆排序原理：
  • 这里讲解的很清楚；
• java实现：

package algorithm;

public class InsertionSort {

	public static void main(String[] args) {
		int[] nums = { 4,1,2,7,3,8,4,5,10 };
		heapSort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}

	public static void heapSort(int[] myArray) {
		for (int i = myArray.length - 1; i >= 0; i--) {
			// i记录了数组中参与重建最大堆的最后一个元素的索引值
			buildMaxHeap(myArray, i);
			// 交换了第一个元素和倒数第myArray.length-1-i个元素
			swap(myArray, 0, i);
		}
	}

	public static void swap(int[] myArray, int a, int b) {
		int tmp;
		tmp = myArray[a];
		myArray[a] = myArray[b];
		myArray[b] = tmp;
	}

	public static void buildMaxHeap(int[] myArray, int i) {
		// (i-1)/2 是数组中最后一个具有叶子节点的节点的索引，从这个节点开始重建堆
		for (int j = (i - 1) / 2; j >= 0; j--) {
			int k = j;
			while (k * 2 + 1 <= i) {
				int leftIndex = k * 2 + 1; // 当前节点的左子节点的索引
				int rightIndex = leftIndex + 1; // 当前节点的右子节点的索引
				int biggerInLeftRight = myArray[leftIndex]; // 左右子节点中较大的数
				int biggerIndex = leftIndex; // 左右子节点中较大的数的索引

				// 判断右子节点是否参与本次重建堆，参与则执行
				if (rightIndex <= i) {
					// 找出左右子节点中较大的数
					if (myArray[leftIndex] < myArray[rightIndex]) {
						biggerInLeftRight = myArray[rightIndex];
						biggerIndex = rightIndex;
					}
				}

				// 将当前节点、当前节点的左右子节点中的最大值移到当前节点的位置
				if (myArray[k] < biggerInLeftRight) {
					swap(myArray, k, biggerIndex);
					// 继续循环，确保当前节点的左右子节点也满足最大堆的性质
					k = biggerIndex;
				} else {
					break;
				}
			}
		}
	}
}

• js实现：

var nums = [8,3,5,0,2,7,9,10];
var heapSort = function(nums){
	for(var i=nums.length-1; i>=0; i--){
		buildMaxHeap(nums,i);
		swap(nums,0,i);
	}
}

var swap = function(nums, a, b){
	var tmp;
	tmp = nums[a];
	nums[a] = nums[b];
	nums[b] = tmp;
}

var buildMaxHeap = function(nums,i){
	for(var j=Math.floor((i-1)/2); j>=0; j--){
		var k = j;
		while(k*2+1<=i){
			var leftIndex = k*2+1;
			var rightIndex = leftIndex+1;
			var biggerIndex = leftIndex;

			if(rightIndex<=i){
				if(nums[leftIndex]<nums[rightIndex]){
					biggerIndex = rightIndex;
				}
			}

			if(nums[k]<nums[biggerIndex]){
				swap(nums,k,biggerIndex);
				k = biggerIndex;
			}else{
				break;
			}
		}
	}
}

heapSort(nums);
for(var i=0; i<nums.length; i++){
	console.log(nums[i]);
}

基数排序（radix sort）

• 基数排序和其他排序方法的思路不同，不是以比较对象大小为基础；
• 基础排序先将待排序对象的长度补全成相同的长度，然后从最后一位开始：将所有元素按照最后一位的大小排序，排序后元素的最后一位是有序的；再将所有元素按照倒数第二位的大小排序，排序后元素的倒数第二位是有序的，在倒数第二位相同的元素中，它们的最后一位是有序的；再将所有元素按照倒数第三位的大小排序，排序后元素的倒数第三位是有序的，在倒数第三位相同的元素中，它们的倒数第二位是有序的，在倒数第二位相同的元素中，它们的最后一位是有序的；
• 以此类推，直到元素的第一位排序完成；
• 此时元素已经是有序序列；
• java实现：

package test8;

public class RadixSort {
	public static void main(String[] args) {
		int[] array = new int[] { 20, 22, 98, 45, 77, 75, 55, 25, 52, 79, 56,
				44, 32, 37, 35, 21, 102, 33, 178, 187, 156, 144 };
		sort(array, 3); // 传入数组和数组中长度最大的数的长度

		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
	}

	public static void sort(int[] array, int d) {
		int[][] bucket = new int[array.length][array.length];

		for (int n = 1, m = 0; m < d; n *= 10, m++) {
			int[] num = new int[array.length];  //记录二维数组bucket的横向数组的长度
			for (int i = 0; i < array.length; i++) {
				int position = array[i] / n % 10;
				bucket[position][num[position]] = array[i];
				num[position]++;
			}
			for (int k = 0, i = 0; k < array.length; k++) {
				for (int j = 0; j < num[k]; j++, i++) {
					array[i] = bucket[k][j];
				}
			}
		}
	}
}

各种排序算法对比

• 资料：

  • 这里有各种算法的汇总，进入相应的算法的词条有动图；
  • 这里有HTML5动图，非常好看；

• 复杂度对比：

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
冒泡排序	O(n)	O(n^2)	O(n^2)	稳定	O(1)
选择排序	O(n^2)	O(n^2)	O(n^2)	不稳定	O(1)
插入排序	O(n)	O(n^2)	O(n^2)	稳定	O(1)
希尔排序	O(n)	O(n^1.5)	O(n^2)	不稳定	O(1)
归并排序	O(n*logn)	O(n*logn)	O(n*logn)	稳定	O(1)
快速排序	O(n*logn)	O(n*logn)	O(n^2)	不稳定	O(logn)~O(n)
堆排序	O(n*logn)	O(n*logn)	O(n*logn)	不稳定	O(1)
基数排序	约为O(n)	约为O(n)	约为O(n)	稳定	O(rd+n)

• 各种排序方法的适用条件
  • 当待排序总数较小，用插入排序或选择排序，虽然他们的时间复杂度高，但是在排序总数较小时时间并不是主要矛盾；
  • 当待排序对象基本有序时，用插入排序、冒泡排序、快速排序，因为他们在序列接近有序的情况下的时间复杂度比序列完全无序时低；
  • 若待排序对象非常多，选择快速排序（首选）、堆排序、归并排序，因为他们的时间复杂度为O(nlgn)，即用空间换取时间，以便解决“时间太长”这个主要矛盾；
  • 若要求排序算法稳定，则选用归并排序；