2019独角兽企业重金招聘Python工程师标准>>> 
以下程序均将数据封装于DataWrap数据包装类中，如下所示：
class DataWrap implements Comparable<DataWrap>
{
int data;
String flag;
public DataWrap(int data,String flag)
{
this.data = data;
this.flag = flag;
}
//重写compareTo方法
public int compareTo(DataWrap other)
{
return this.data > other.data ? 1 : (this.data == other.data ? 0 : -1);
}
public String toString()
{
return this.data + this.flag;
}
}
一、选择排序
1、直接选择排序
数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，直到整个数组变有序区。
1 public static void directSelectSort(DataWrap[] dw)
2 {
3 int n = dw.length;
4 for(int i = 0;i < n-1;i++)
5 {
6 int minIndex = i;
7 for(int j = i+1;j < n;j++)
8 {
9 if(dw[minIndex].compareTo(dw[j]) > 0)
10 {
11 minIndex = j; //minIndex为每趟比较重最小数的索引
12 }
13 }
14 swap(dw,minIndex,i);
15 System.out.println("直接选择排序中的元素：" + Arrays.toString(dw));
16 }
17
18 }2、堆排序
1)二叉堆
二叉堆是完全二叉树或者是近似完全二叉树。
父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
2)堆的存储
一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
3)堆排序原理(以最小堆为例)
堆排序是先建立一个最小堆，然后第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复最小堆。第二次将A[0]与A[n – 2]交换，再对A[0，…，n - 3]重新恢复最小堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序(为降序)了。
建立最小堆就是先从最后一个非叶子节点(即n/2-1节点)开始，节点依次往前就行，直到第二个节点。对于每个节点，先比较其左右节点选出较小的节点，然后将较小的节点与父节点进行比较。如果父节点比最小的子节点还小的话则不需要调整，否则的话将较小的子节点作为新的父节点，将原先的父节点与其子节点的子节点中较小的进行比较，直到该父节点找到能够插入的位置或者是到达堆的结束。
4)代码实现
1 public class HeapSort
2 {
3 /**
4 * 从某一节点向下调整大小
5 * @param dw 待排序数据包
6 * @param i 开始向下调整的堆索引
7 * @param n 所调整堆数据的大小
8 */
9 public static void MinHeapFixDown(DataWrap[] dw,int i,int n)
10 {
11 int j;
12 DataWrap temp;
13 j = 2 * i +1;
14 temp = dw[i];
15 while(j < n)
16 {
17 if(j+1 < n && dw[j+1].compareTo(dw[j]) < 0)
18 { //找出左右子节点中较小的
19 j++;
20 }
21 if(temp.compareTo(dw[j]) <= 0)
22 { //将父节点与子节点进行比较
23 break;
24 }
25 dw[i] = dw[j]; //将较小的子节点上移
26 i = j;
27 j = 2 * i +1;
28 }
29 dw[i] = temp;
30 }
31 //构建最小堆并进行堆排序
32 public static void heapSort(DataWrap[] dw)
33 {
34 int n = dw.length;
35 //构建最小堆
36 for(int i = n/2-1;i >= 0;i--)
37 {
38 HeapSort.MinHeapFixDown(dw, i, n);
39 }
40 //堆排序
41 for(int i = n-1;i >=1;i--)
42 {
43 swap(dw,0,i); //每次将第n-1,n-2,...1个元素与dw[0]交换后，将最后一个元素从堆中排除
44 MinHeapFixDown(dw, 0, i); //将每次交换后-1的堆从dw[0]开始，调整为新的最小堆
45 }
46 }
47
48 //交换DataWrap数组中i,j两数值
49 public static void swap(DataWrap[] dw,int i,int j)
50 {
51 DataWrap temp;
52 temp = dw[i];
53 dw[i] = dw[j];
54 dw[j] = temp;
55 }
56
57 public static void main(String[] args)
58 {
59 DataWrap[] dw = {new DataWrap(25,""),new DataWrap(42,""),new DataWrap(36,""),new DataWrap(8,""),new DataWrap(78,""),new DataWrap(99,"")};
60 System.out.println("待排序数据为：" + Arrays.toString(dw));
61 HeapSort.heapSort(dw);
62 System.out.println("排序后数据为：" + Arrays.toString(dw));
63 }
64 }二、交换排序
1、冒泡排序
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
1 public static void bubbleSort(DataWrap[] dw)
2 {
3 int n = dw.length;
4 boolean flag;//设置标志位，若发生未交换的情况，说明已经有序，退出循环即可
5 for(int i = n-1;i > 0 ;i--)
6 {
7 flag = false;
8 for(int j = 0;j < i;j++)
9 {
10 if(dw[j].compareTo(dw[j+1]) > 0)
11 {
12 swap(dw,j+1,j);
13 flag = true;
14 }
15 }
16 if(!flag)
17 {
18 break;
19 }
20 System.out.println("排序中顺序：" + Arrays.toString(dw));
21 }
22 }2、快速排序
快速选择排序主要思路是：
“挖坑填数+分治法”，首先令i =L; j = R; 将a[i]挖出形成第一个坑，称a[i]为基准数。然后j--由后向前找比基准数小的数，找到后挖出此数填入前一个坑a[i]中，再i++由前
向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中，这样i之前的数都比基准数小，i之后的数都比基准数
大。因此将数组分成二部分再分别重复上述步骤就完成了排序。
public class QuickSort {
static int partition(int[] data, int left, int high) {
int midData = data[left];
while (left < high) {
while (left < high && midData < data[high])
high--;
data[left] = data[high];
while (left < high && midData >= data[left])
left++;
data[high] = data[left];
}
data[left] = midData;
return left;
}
/**
* 快速排序
*
* @param data
* @param left
* @param high
*/
static void quick_sort(int[] data, int left, int high) {
int loc = 0;
if (left < high) {
loc = partition(data, left, high);
quick_sort(data, left, loc - 1);
quick_sort(data, loc + 1, high);
}
}
public static void main(String[] args) {
int[] data = {6, 2, 4, 8, 5, 9};
quick_sort(data, 0, data.length - 1);
System.out.print("排序后数据为:" + Arrays.toString(data));
}
}三、插入排序
1、直接插入排序
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
public static void directInsertSort(DataWrap[] dw,int n)
2 {
3 for(int i = 1;i < n;i++)
4 {
5 if(dw[i].compareTo(dw[i-1]) < 0)
6 {
7 DataWrap temp = dw[i];
8 int j;
9 for(j = i-1;j >= 0 && dw[j].compareTo(temp) > 0;j--)
10 {
11 dw[j+1] = dw[j];
12 }
13 dw[j+1] = temp;
14 }
15 }
16 }2、希尔排序(Shell排序、缩小增量排序)
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”
public static void directInsertSort(DataWrap[] dw,int n)
2 {
3 for(int i = 1;i < n;i++)
4 {
5 if(dw[i].compareTo(dw[i-1]) < 0)
6 {
7 DataWrap temp = dw[i];
8 int j;
9 for(j = i-1;j >= 0 && dw[j].compareTo(temp) > 0;j--)
10 {
11 dw[j+1] = dw[j];
12 }
13 dw[j+1] = temp;
14 }
15 }
16 }四、归并排序
当一个数组左边和右边都有序时，将两边合并就完成了排序，而要使两边都有序，则需要用递归。先递归下去，再合并上来，就是归并排序。
1 public class MergeSort
2 {
3
4 public static void mergeSort(int[] data)
5 {
6 int n = data.length;
7 sort(data, 0, n-1);//归并排序
8 }
9
10 public static void sort(int[] data,int left,int right)
11 {
12 if(left <right)
13 {
14 int center = (left + right)/2;//中间索引
15 sort(data, left, center);//堆左边数组进行递归
16 sort(data, center+1, right);//堆右边数组进行递归
17 merge(data, left, center, right);//合并
18 }
19 }
20
21 public static void merge(int[] data,int left,int center,int right)
22 {
23 int[] array = new int[data.length];//定义临时数组
24 int mid = center+1;
25 int k = left;//临时数组索引
26 int temp = left;
27 while(left <= center && mid <= right)
28 {
29 if(data[left] < data[mid])
30 array[k++] = data[left++];
31 else
32 array[k++] = data[mid++];
33 }
34 while(left <= center)
35 array[k++] = data[left++];
36 while(mid <= right)
37 array[k++] = data[mid++];
38 while(temp <= right)
39 data[temp] = array[temp++];
40 }
41
42 public static void main(String[] args)
43 {
44 int[] data = {2,27,56,8,24,12,99,0,56};
45 MergeSort.mergeSort(data);
46 for(int i:data)
47 {
48 System.out.print(i + ",");
49 }
50 }
51 }