转载算法和数据结构 — 八种必须掌握的排序
排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。 在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。 首先来看一下八种排序之间的关系图
1、 直接插入排序
（1）基本思想：
在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
（2）理解图：
已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08
开始排序
（3）代码实现
public void insertSort(
int[] a) {
int i, j, temp;
for (i =
1; i < a.length; i++) {
temp = a[i];
for (j = i; j >
0 && temp < a[j -
1]; j--) {
a[j] = a[j -
1];
}
a[j] = temp;
}
for (i =
0; i < a.length; i++) {
System.out.print(a[i] +
"\t");
}
}
直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法。
2、希尔排序（最小增量排序）
（1）基本思想：
算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直 接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
（2）理解图
（3）代码实现
public void shellSort(
int[] a) {
int temp =
0;
double d1 = a.length;
while (
true) {
d1 = Math.ceil(d1 /
2);
int d = (
int) d1;
for (
int x =
0; x < d; x++) {
for (
int i = x + d; i < a.length; i += d) {
int j = i - d;
temp = a[i];
for (; j >=
0 && temp < a[j]; j -= d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if (d ==
1) {
break;
}
}
for (
int i =
0; i < a.length; i++)
System.out.print(a[i] +
"\t");
}
3、简单选择排序
（1）基本思想：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
（2）理解图
第一次 ： 08最小 和21交换位置 第二次： 除第一个位置的08外 16最小 和25交换位置 以此类推
（3）代码实现
public static void selectSort(
int[] a) {
int position =
0;
for (
int i =
0; i < a.length; i++) {
int j = i +
1;
position = i;
int temp = a[i];
for (; j < a.length; j++) {
if (a[j] < temp) {
temp = a[j];
position = j;
}
}
a[position] = a[i];
a[i] = temp;
}
for (
int i =
0; i < a.length; i++)
System.out.print(a[i] +
"\t");
}
4、堆排序
（1）基本思想：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。 堆的定义如下：具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi& lt;=h2i,hi<=2i+1）(i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。 由堆的定义可以看出，堆顶元素（即第一 个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。 堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二 叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。 依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后 一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
（2）实例：
初始序列：46,79,56,38,40,84
建堆：
交换，从堆中踢出最大数
剩余结点再建堆，再交换踢出最大数
依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。
（3）代码：
/**
* 选择排序之堆排序：
*
* 1. 基本思想： 堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，
* 利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
*
* 2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤[N/2])
* 堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，
* 它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。
* 反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
*
* 3.排序过程： 堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：
* 将当前无序区调整为一个大根堆
* ，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
*/
public class HeapSort {
/**
* 排序算法的实现，对数组中指定的元素进行排序
*
* @param array
* 待排序的数组
* @param c
* 比较器
*/
public void sort(Integer[] arr) {
initialHeap(arr);
for (
int i = arr.length; i >=
2; i--) {
swap(arr,
0, i -
1);
adjustNote(arr,
1, i -
1);
}
}
/**
* @param arr
* 排序数组
* @param c
* 比较器
*/
private void initialHeap(Integer[] arr) {
int lastBranchIndex = arr.length /
2;
for (
int i = lastBranchIndex; i >=
1; i--) {
adjustNote(arr, i, arr.length );
}
}
/**
* 调整节点顺序，从父、左右子节点三个节点中选择一个最大节点与父节点转换
*
* @param arr
* 待排序数组
* @param parentNodeIndex
* 要调整的节点，与它的子节点一起进行调整
* @param len
* 树的节点数
* @param c
* 比较器
*/
private void adjustNote(Integer[] arr,
int parentNodeIndex,
int len) {
int maxValueIndex = parentNodeIndex;
if (parentNodeIndex *
2 <= len) {
if ((arr[parentNodeIndex -
1]
.compareTo(arr[parentNodeIndex *
2 -
1])) <
0) {
maxValueIndex = parentNodeIndex *
2;
}
if (parentNodeIndex *
2 +
1 <= len) {
if ((arr[maxValueIndex -
1]
.compareTo(arr[(parentNodeIndex *
2 +
1) -
1])) <
0) {
maxValueIndex = parentNodeIndex *
2 +
1;
}
}
}
if (maxValueIndex != parentNodeIndex) {
swap(arr, parentNodeIndex -
1, maxValueIndex -
1);
if (maxValueIndex *
2 <= len) {
adjustNote(arr, maxValueIndex, len);
}
}
}
/**
* 交换数组中的两个元素的位置
*
* @param array
* 待交换的数组
* @param i
* 第一个元素
* @param j
* 第二个元素
*/
public void swap(Integer[] array,
int i,
int j) {
if (i != j) {
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
Integer[] a = {
6,
9,
0,
4,
5,
9,
1,
4,
2,
6,
3,
8,
0,
7,
0, -
7, -
1,
34 };
HeapSort heapsort =
new HeapSort();
heapsort.sort(a);
for (Integer arrValue : a) {
System.out.print(arrValue +
" ");
}
}
}
5、冒泡排序
（1）基本思想：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
（2）理解图
（3）代码实现
/**
* 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，
* 如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，
* 也就是说该数列已经排序完成。
* 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
* 步驟：
* 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
* @author Administrator
*
*/
public class bubbleSort {
public bubbleSort() {
int a[] = {
49,
38,
65,
97,
76,
13,
27,
49,
78,
34,
12,
64,
5,
4,
62,
99,
98,
54,
56,
17,
18,
23,
34,
15,
35,
25,
53,
51 };
int temp =
0;
for (
int i =
0; i < a.length -
1; i++) {
for (
int j =
0; j < a.length -
1 - i; j++) {
if (a[j] > a[j +
1]) {
temp = a[j];
a[j] = a[j +
1];
a[j +
1] = temp;
}
}
}
for (
int i =
0; i < a.length; i++)
System.out.println(a[i]);
}
}
6、快速排序
（1）基本思想：
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
（2）理解图
（3）代码实现
/**
* 快速排序是其基本思想是基本思想是，通过一趟排序将待排记录分隔成独立的两部分，
* 其中一部分记录的关键字均比另一部分的关键字小，
* 则可分别对这两部分记录继续进行排序，以达到整个序列有序。
* 步驟：
* 1、从数列中挑出一个元素，称为 "基准"（pivot），
2、重新排序数列，所有元素比基准值小的摆放在基准前面，
所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，
该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* @author Administrator
*
*/
public class QuickSort {
public void sort(){
int a[] = {
11,
33,
44,
2,
0,
1,
49,
38,
65,
97,
76,
13,
27,
49,
78,
34,
12,
64,
5,
4,
62,
99,
98,
54,
56,
17,
18,
23,
34,
15,
35,
25,
53,
51,
90 };
quickSort(a,
0,a.length-
1);
for (
int i =
0; i < a.length; i++) {
System.out.print(a[i]+
" ");
}
}
/**
*
* @param a 待排序数组
* @param low 可以看做低位助手
* @param high 可以看做高位助手
* 低助手是用来找比基准位大的数
* 高助手是用来找比基准位小的数 这样就可以看做两个助手在活动
*/
private void quickSort(
int[] a,
int low,
int high) {
int start=low;
int end=high;
int base=a[low];
int tempIndex=low;
while(low<high){
while(low<high&&base<=a[high]){
high--;
}
a[low]=a[high];
tempIndex=high;
while(low<high&&base>=a[low]){
low++;
}
a[high]=a[low];
tempIndex=low;
a[tempIndex]=base;
}
if(low-start>
1){
quickSort(a,
0,low-
1);
}
if(end-high>
1){
quickSort(a,high+
1,end);
}
}
public static void main(String[] args) {
QuickSort q=
new QuickSort();
q.sort();
}
}
7、归并排序
（1）基本排序：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
（2）理解图：
递归分解：
下面的图理解合并
（3）、实现代码
import java.util.Arrays;
/**
* 归并排序是建立在归并操作上的一种有效的排序算法。
* 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
* 归并排序是一种稳定的排
* 步骤：
1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
2、Conquer: 对这两个子序列分别采用归并排序。
3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。
* @author Administrator
*
*/
public class mergineSort {
int a[] = {
49,
38,
65,
97,
76,
13,
27,
49,
78,
34,
12,
64,
5,
4,
62,
99,
98,
54,
56,
17,
18,
23,
34,
15,
35,
25,
53,
51 };
public mergineSort() {
sort(a,
0, a.length -
1);
for (
int i =
0; i < a.length; i++)
System.out.println(a[i]);
}
/**
*
* @param data 待排序数组
* @param left 数组起始位置
* @param right 数组结束位置
*/
public void sort(
int[] data,
int left,
int right) {
if (left < right) {
int center = (left + right) /
2;
sort(data, left, center);
sort(data, center +
1, right);
merge(data, left, center, right);
}
}
/**
*
* @param data排序完的原数组
* @param left 起始位置
* @param center 中间位置
* @param right 结束位置
*/
public void merge(
int[] data,
int left,
int center,
int right) {
int[] tmpArr =
new int[data.length];
int mid = center +
1;
int temp = left;
while (left <= center && mid <= right) {
if (data[left] <= data[mid]) {
tmpArr[temp] = data[left];
left++;
temp++;
}
else {
tmpArr[temp] = data[mid];
mid++;
temp++;
}
}
while (mid <= right) {
tmpArr[temp] = data[mid];
mid++;
temp++;
}
while (left <= center) {
tmpArr[temp] = data[left];
left++;
temp++;
}
for(
int i=
0;i<=right;i++){
data[i]=tmpArr[i];
}
}
}
8、基数排序
（1）基本思想：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
（2）理解图
（3）实现代码
/**
* 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
* 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，
* 所以基数排序也不是只能使用于整数。
* 步驟：
* 1、将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
2、从最低位开始，依次进行一次排序。
3、这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
* @author Administrator
*
*/
public class RadixSort {
public static int[]
radixSortAsc(
int[] arr) {
for (
int d =
1; d <= getMax(arr); d++) {
int[] tmpArray =
new int[arr.length];
int[] count =
new int[
10];
for (
int i =
0; i < arr.length; i++) {
count[digit(arr[i], d)] +=
1;
}
for (
int i =
1; i <
10; i++) {
count[i] += count[i -
1];
}
for (
int i = arr.length -
1; i >=
0; i--) {
tmpArray[count[digit(arr[i], d)] -
1] = arr[i];
count[digit(arr[i], d)]--;
}
for(
int i=
0;i<arr.length;i++){
arr[i]=tmpArray[i];
}
}
return arr;
}
public static int getMax(
int[] array) {
int max = array[
0];
for (
int j =
1; j < array.length; j++) {
if (array[j] > max) {
max = array[j];
}
}
int time =
0;
while (max >
0) {
max /=
10;
time++;
}
return time;
}
/**
* 取数xxx上的第d位数字
*
* @param x
* 数字
* @param d
* 第几位，从低位到高位
* @return
*/
public static int digit(
int num,
int d) {
int pow =
1;
while (--d >
0) {
pow *=
10;
}
return num / pow %
10;
}
public static void main(String[] args) {
int[] data = {
73,
22,
93,
43,
55,
14,
28,
65,
39,
81,
33,
10 };
System.out.println(radixSortAsc(data));
for (
int i =
0; i < data.length; i++) {
System.out.print(data[i] +
" ");
}
}
}
