排序
选择排序（n*n）、快速排序（n*log2 n）、希尔排序(n*1.2次方)、堆排序（n*log2 n）不是稳定的排序算法，
冒泡排序（n*n）、插入排序（n*n）、归并排序（n*log2 n）
和基数排序是稳定的排序算法。
（1）冒泡排序
//冒泡排序：
public class bubbleSort {
public static void main(String[] args) {
int a[]={12,1,3,24,4};
int temp=0;
int i;
int j;
for(i=0;i<a.length;i++)
{
for(j=0;j<a.length-i-1;j++)
{
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
System.out.println("冒泡排序");
for(int k=0;k<a.length;k++)
System.out.print(a[k]+" ");
}
}
（2）快速排序
public class quickSort {
public static void main(String[] args){
int a[]={12,45,2,56,1,36,4};
System.out.print("排序前\n");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.print("\n");
System.out.print("排序后\n");
quickSort(a,0,a.length-1);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
}
public static void quickSort(int[] numbers, int start, int end) {
if (start < end) {
int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）
int temp; //
记录临时中间值
int i = start, j = end;
do {
while ((numbers[i] < base) && (i < end))
i++;
while ((numbers[j] > base) && (j > start))
j--;
if (i <= j) {
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j)
quickSort(numbers, start, j);
if (end > i)
quickSort(numbers, i, end);
}
}
}
（3）堆排序 叶节点n/2+1~n,父节点：1~n/2，最大堆是升序排序
public class heapSort {
public static int heap_size;
//双亲编号
public static int parent(int i){
return i/2;
}
//左孩子编号
public static int leftChild(int i){
return 2*i;
}
//右孩子编号
public static int rightChild(int i){
return 2*i + 1;
}
/**
* 保持最大堆的性质
* @param a，堆中的数组元素
* @param i，对以该元素为根元素的堆进行调整，假设前提：左右子树都是最大堆
*
* 由于左右孩子都是最大堆，首先比较根元素与左右孩子，找出最大值，假如不是根元素，则调整两个元素的值；
* 由于左孩子（右孩子）的值与根元素交换，有可能打破左子树（右子树）的最大堆性质，因此继续调用，直至叶子元素。
*/
public static void max_heapify(int[] a, int i){
int left = leftChild(i);
int right = rightChild(i);
int largest = 0;
/* if(left < heap_size && a[i]<a[left]){
largest = left;
}else{
largest = i;
}
if(right < heap_size && a[right] > a[largest]){
largest = right;
}
if(largest == i){
return ;
}else{
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(a, largest);
} */
if(left < heap_size && a[i]<a[left]){
int temp = a[i];
a[i] = a[left];
a[left] = temp;
max_heapify(a, left);
}
if(right < heap_size && a[i]<a[right]){
int temp = a[i];
a[i] = a[right];
a[right] = temp;
max_heapify(a, right);
}
}
/**
* 建立最大堆。在数据中，a.length/2+1一直到最后的元素都是叶子元素，也就是平凡最大堆，因此从其前一个元素开始，一直到
* 第一个元素，重复调用max_heapify函数，使其保持最大堆的性质
* @param a
*/
public static void build_max_heap(int[] a){
for(int i = a.length/2; i>=0; i--){
max_heapify(a, i);
}
}
/**
* 堆排序：首先使用建立最大堆的算法建立好最大堆，然后将堆顶元素（最大值）与最后一个值交换，同时使得
* 堆的长度减小1 ，调用保持最大堆性质的算法调整，使得堆顶元素成为最大值，此时最后一个元素已被排除在外、
*/
public static void heapSort(int[] a){
build_max_heap(a);
for(int i = a.length - 1; i>=1; i--){
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heap_size--;
max_heapify(a,0);
}
}
public static void main(String[] args) {
int a[] = {4, 0, 1, 3, 2, 16, 9, 10,14, 8, 7};
heap_size = a.length;
heapSort(a);
for(int i = 0; i< a.length; i++){
System.out.print(a[i] + " ");
}
}
}
