十大排序算法

以下体会不知大家可曾感同身受:

1、十大排序算法，感觉理解了，却写不下来。

2、一个一个写下来，没什么问题，但是一口气，写完十大排序算法，却困难重重，错误百出。

3、哪怕当时写下来了，过了一段时间却忘了。

今天我之所以要写这篇文章，是因为上述问题，我都曾体会过。而且曾经一度怀疑人生。但是今天我克服上述问题。这不是因为我IQ提高或者记忆力加强的缘故。而是因为我调整学习的策略。在前行的途中，我们中并不乏勇敢者。它们不怕吃苦，奋力拼搏。却仍然无法摆脱平庸。其中原因，除不可抗力因素(资源、天赋等)。而大多人更多是因为方式方法。我想说:“不要轻易怀疑自己，不要轻言放弃。”，下面我谈谈自己学习十大排序算法的心得。

策略

总结主要有一下几点:

1、分清难易、循序渐进、逐步突破。

十大排序算法(冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序)。冒泡排序、选择排序、插入排序可能是相对容易的。但学好这三大排序，对理解更高级排序算法，是大有裨益的。

2、不要把算法孤立起来，尝试分析各个算法之间的区别和联系

我先来抛砖引玉下:

(1) 希尔排序，是在插入排序的基础上，引入了分组的概念。

(2) 快速排序，结合了冒泡排序和归并排序的特点。

(3) 堆排序的算法跟插入排序有点像。

(4) 通排序，小桶排序引入插入排序或者快速排序

(5) 计数排序、基数排序、桶排序是姊妹篇。算法有极高的相似度。

3、各个算法之间的核心特征。

这些可以查看网络对十大排序算法的介绍。

4、反复练习，加深理解。最好能用自己最擅长的理解方式，去解释他。切记不要死记硬背。

代码实现

1、冒泡排序

public void bubbleSort(int[] arr) {
	int i,j;
	for(i = 1; i < arr.length; i++) {
		for(j = 0; j < arr.length - i; j++) {
			if (arr[j] > arr[j+1]) {
				swap(arr, j, j+1);
			}
		}
	}
}

2、选择排序

public void selectSort(int[] arr) {
	int i,j, minIndex;
	for(i = 0; i < arr.length - 1; i++) {
		minIndex = i;
		for(j = i+1; j < arr.length; j++) {
			if (arr[minIndex] > arr[j]) {
				minIndex = j;
			}
		}
		if (minIndex != i) {
			swap(arr, minIndex, i);
		}
	}
}

3、插入排序

public void insertSort(int[] arr) {
	int i,j, insertIndex,tmp;
	for(i = 1; i < arr.length; i++) {
		insertIndex = i;
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] > tmp) {
				arr[j+1] = arr[j];
				insertIndex = j;
			}
		}
		if (insertIndex != i) {
			arr[insertIndex] = tmp;
		}
	}
}

4、希尔排序

public void shellSort(int[] arr) {
		
	int gap = 1;
	while(gap < arr.length) {
		gap = gap * 3 + 1;
	}
		
	while(gap > 0) {
		for(int i = gap; i < arr.length; i++) {
			int insertIndex = i;
			int tmp = arr[i];
			for(int j = i - gap; j >= 0; j -= gap) {
				if (arr[j] > tmp) {
					arr[j+gap] = arr[j];
					insertIndex = j;
				}
			}
			if (insertIndex != i) {
				arr[insertIndex] = tmp;
			}
		}
		gap = (int) Math.floor(gap/3);
	}
}

5、归并排序

public class MergeSort {
	public int[] mergeSort(int[] sourceArray) {
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		return sort(arr);
	}
	
	public int[] sort(int[] arr) {
		if (arr.length < 2) {
			return arr;
		}
		int middle = (int) Math.floor(arr.length/2);
		int[] left = Arrays.copyOfRange(arr, 0, middle);
		int[] right = Arrays.copyOfRange(arr, middle, arr.length);
		return merge(sort(left), sort(right));
	}
	
	public int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int i = 0;
		while(left.length > 0 && right.length > 0) {
			if (left[0] < right[0]) {
				result[i++] = left[0];
				left = Arrays.copyOfRange(left, 1, left.length);
			} else {
				result[i++] = right[0];
				right = Arrays.copyOfRange(right, 1, right.length);
			}
		}
		
		if (left.length > 0) {
			for(int value:left) {
				result[i++] = value;
			}
		}
		
		if (right.length > 0) {
			for(int value:right) {
				result[i++] = value;
			}
		}
		return result;
	}
}

6、快速排序

package com.ssuqin_kk;

import java.util.Arrays;

public class QuickSort {
	public int[] sort(int[] sourceArray) {
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		quickSort(arr, 0, arr.length - 1);
		return arr;
	}
	
	public void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int index = partition(arr, left, right);
			quickSort(arr, left, index - 1);
			quickSort(arr, index + 1, right);
		}
	}
	
	public void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
	
	public int partition(int[] arr, int left, int right) {
		int pivot = left;
		int index = pivot + 1;
		for(int i = index; i <= right; i++) {
			if (arr[i] < arr[pivot]) {
				swap(arr, i, index);
				index++; 
			}
		}
		swap(arr, pivot, index - 1);
		return index - 1;
	}
}

7、堆排序

package com.ssuqin_kk;

import java.util.Arrays;

public class HeapSort {
	public int[] sort(int[] sourceArray) {
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		heapSort(arr);
		return arr;
	}
	
	public void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
	
	public void heapSort(int[] arr) {
		for(int i = (int) Math.floor(arr.length/2) - 1; i >= 0; i--) {
			adjustHeap(arr, i, arr.length);
		}
		
		for(int j = arr.length - 1; j > 0; j--) {
			swap(arr, 0, j);
			adjustHeap(arr, 0, j);
		}
	}
	
	public void adjustHeap(int[] arr, int i, int length) {
		int tmp = arr[i];
		for(int k = 2*i + 1; k < length; k = 2 * k + 1) {
			if ((k + 1) < length && arr[k+1] > arr[k]) {
				k++;
			}
			
			if (arr[k] > tmp) {
				arr[i] = arr[k];
				i = k;
			} else {
				break;
			}
		}
		
		arr[i] = tmp;
	}
}

8、计数排序

package com.ssuqin_kk;

import java.util.Arrays;

public class CountingSort {
	public int[] sort(int[] sourceArray) {
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		int maxValue = getMaxValue(arr);
		countingSort(arr, maxValue);
		return arr;
	}
	
	public int getMaxValue(int[] arr) {
		int maxValue = arr[0];
		for(int value:arr) {
			if (value > maxValue) {
				maxValue = value;
			}
		}
		return maxValue;
	}
	
	public void countingSort(int[] arr, int maxValue) {
		int[] buckets = new int[maxValue + 1];
		
		for(int i = 0; i < arr.length; i++) {
			buckets[arr[i]]++;
		}
		
		int sortedIndex = 0;
		for(int i = 0; i < buckets.length; i++) {
			while(buckets[i] > 0) {
				arr[sortedIndex++] = i;
				buckets[i]--;
			}
		}
	}
}

9、桶排序

package com.ssuqin_kk;

import java.util.Arrays;

public class BucketSort {
	public int[] sort(int[] sourceArray) {
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		bucketSort(arr, 5);
		return arr;
	}
	
	public int[] arrAppend(int[] arr, int value) {
		arr = Arrays.copyOf(arr, arr.length + 1);
		arr[arr.length - 1] = value;
		return arr;
	}
	
	public void bucketSort(int[] arr, int bucketSize) {
		int minValue = arr[0];
		int maxValue = arr[0];
		
		for(int value:arr) {
			if (value < minValue) {
				minValue = value;
			} else if (value > maxValue) {
				maxValue = value;
			}
		}
		
		int bucketCount = (int) Math.floor((maxValue - minValue)/bucketSize) + 1;
		int[][] buckets = new int[bucketCount][0];
		
		for (int i = 0; i < arr.length; i++) {
			int index = (int) Math.floor((arr[i] - minValue)/bucketSize);
			buckets[index] = arrAppend(buckets[index], arr[i]);
		}
		
		int sortedIndex = 0;
		for(int i = 0; i < bucketCount; i++) {
			if (buckets[i].length <= 0) {
				continue;
			}
			buckets[i] = new QuickSort().sort(buckets[i]);
			for(int value:buckets[i]) {
				arr[sortedIndex++] = value;
			}
		}
	}
}

10、基数排序

package com.ssuqin_kk;

import java.util.Arrays;

public class RadixSort {
	
	public void print(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	
	public int[] radix_sort(int[] sourceArray) {
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		int maxValue = getMaxValue(arr);
		for(int exp = 1; maxValue/exp > 0; exp *= 10) {
			count_sort(arr, exp, arr.length);
		}
		return arr;
	}
	
	public int getMaxValue(int[] arr) {
		int maxValue = arr[0];
		for(int value:arr) {
			if (value > maxValue) {
				maxValue = value;
			}
		}
		return maxValue;
	}
	
	public void count_sort(int[] arr, int exp, int length) {
		int[] output = new int[length];
		int[] buckets = new int[10];
		
		for(int i = 0; i < length; i++) {
			int index = (int) Math.floor(arr[i]/exp%10);
			buckets[index]++;
		}
		
		for(int i = 1; i < buckets.length; i++) {
			buckets[i] += buckets[i-1];
		}
		
		for(int i = arr.length - 1; i >= 0; i--) {
			int index = (int) Math.floor(arr[i]/exp%10);
			output[buckets[index] - 1] = arr[i];
			buckets[index]--;
		}
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = output[i];
		}
		
		print(arr);
	}
}