冒泡、插入、歸並、堆排序、快速排序的Java實現代碼

冒泡、插入、歸並、堆排序、快速排序的Java實現代碼，詳細過程就不表了，看代碼吧

import java.util.Arrays;

public class Sort {

static int swapTimes=0;
public static void main(String[] args) {
int[] numbers = { 7, 6, 5, 3, 1, 8, 9, 7, 1, 2 ,5};
//*** BubbleSort Test ***
//bubbleSort(numbers);

//*** InsertSort Test ***
//insertSort(numbers);

//*** MergeSort Test ***
//mergeSort(numbers);

//*** HeapSort Test ***
//heapSort(numbers);

//*** QuickSort Test ***

quickSort(numbers);
System.out.println("result:"+Arrays.toString(numbers));

}

/*
* 插入排序
*/
public static void insertSort(int[] numbers) {
System.out.println("InsertSort:"+Arrays.toString(numbers));
if (numbers == null) {
System.out.println("Invalid input!");
return;
}
for (int i = 1; i < numbers.length; i++) {
int temp=numbers[i];
int j=i-1;
for (; j >= 0&&numbers[j]>temp; j--) { //這個數大於比較數，就把這個數右移
numbers[j + 1] = numbers[j];
System.out.println(Arrays.toString(numbers)+"---temp="+temp);
}
numbers[j+1]=temp; //把比較數賦值到正確位置
System.out.println(Arrays.toString(numbers));
}
}

/*
* 冒泡排序
*/
public static void bubbleSort(int[] numbers) {
System.out.println("BubbleSort:");
if (numbers == null) {
System.out.println("Invalid input!");
return;
}
for (int i = numbers.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (numbers[j] > numbers[j + 1]) {
swap(numbers, j, j + 1);
}
}
}
System.out.println("result:");
}
/*
* 歸並排序
*/
public static void mergeSort(int[] numbers){
if(numbers==null){
System.out.println("Invalid input!");
return;
}
mergeSort(numbers,0,numbers.length-1);
}

private static void mergeSort(int[] numbers, int start, int end) {
if(start>=end){
return;
}
int mid=(start+end)>>1;
mergeSort(numbers, start, mid);
mergeSort(numbers, mid+1, end);
merge(numbers,start,mid,end);
System.out.println(Arrays.toString(numbers)+"---mid="+mid);
}
/*
* 合並兩個有序數組
*/
private static void merge(int[] numbers, int start, int mid, int end) {
int leftLength=mid-start+1;
int rightLength=end-mid;
int[] leftNumbers=new int[leftLength];
int[] rightNumbers=new int[rightLength];
for (int i = 0; i < leftLength; i++) {//將左邊的元素賦給left數組
leftNumbers[i]=numbers[start+i];
}
for (int j = 0; j < rightLength; j++) {//同理
rightNumbers[j]=numbers[mid+j+1];
}
int pLeft=0;
int pRight=0;
for(int index=start;index<=end;index++){//開始merge左右數組
if(pLeft==leftLength){ //當left數組合並完了，就直接賦值right數組
numbers[index]=rightNumbers[pRight++];
}else if(pRight==rightLength){
numbers[index]=leftNumbers[pLeft++];
}else{ //左右數組都沒賦值完，就要比較大小
if(leftNumbers[pLeft]<=rightNumbers[pRight]){
numbers[index]=leftNumbers[pLeft++];
}else{
numbers[index]=rightNumbers[pRight++];
}
}
}
}
/*
* 堆排序
*/
public static void heapSort(int[] numbers){
if(numbers==null){
System.out.println("Invalid input!");
return;
}
int[] heap=buildHeap(numbers); //構造小頂堆
System.out.println("build Heap:"+Arrays.toString(heap));
int index=0;
while(!isHeapEmpty(heap)){
//注意，這裡不能在前面的index++，因為會先算左括號內的++，造成傳入的index+1
numbers[index]=popHeapTop(heap,index++);

}
}
//將堆頂元素pop出來
private static int popHeapTop(int[] heap,int index) {
int temp=heap[0];
int end=heap.length-1-index;
heap[0]=heap[end]; //將最後一個數移至堆頂
heap[end]=Integer.MAX_VALUE;
adjustHeap(heap, 0); //調整堆
System.out.println("current Heap:"+Arrays.toString(heap));
return temp;
}

private static boolean isHeapEmpty(int[] heap) {
if(heap[0]==Integer.MAX_VALUE){
return true;
}
return false;
}
/*
* 構造小頂堆
*/
private static int[] buildHeap(int[] numbers) {
int[] heap=new int[numbers.length];
for(int i=0;i<heap.length;i++){
heap[i]=numbers[i];
}
for(int j=(heap.length>>1)-1;j>=0;j--){ //從有孩子的結點開始，從底向上維護堆
adjustHeap(heap,j);
}
return heap;
}
/*
* 維護堆
*/
private static void adjustHeap(int[] heap, int j) {
int left=j<<1;
int right=(j<<1)+1;
int largest=j;
if(left<heap.length //該左孩子下標必須在數組內
&&heap[left]!=Integer.MAX_VALUE //該元素必須未被覆蓋
&&heap[j]<heap[left]){
largest=left;
}
if(right<heap.length
&&heap[right]!=Integer.MAX_VALUE
&&heap[largest]<heap[right]){
largest=right;
}

if(largest!=j){
swap(heap, j, largest);
adjustHeap(heap, largest); //繼續往下調整
}

}

/*
* 快速排序
*/
public static void quickSort(int[] numbers){
if(numbers==null){
System.out.println("Invalid input!");
return;
}
System.out.println("QuickSort:");
quickSort(numbers,0,numbers.length-1);
}
private static void quickSort(int[] numbers, int start, int end) {
if(start<end){
int mid=patition(numbers,start,end);
quickSort(numbers, start, mid-1);
quickSort(numbers, mid+1, end);
}

}
/*
* 選一個數，將小於它的數放在左邊，大於它的放在右邊
*/
private static int patition(int[] numbers, int start, int end) {
int small=start-1;
int index=start;
int temp=numbers[end]; //選擇數組最後一個元素作為比較數
while(index<=end){
if(numbers[index]<temp){
small++;
if(index!=small){
swap(numbers, small, index);
}
}
index++;
}
swap(numbers, small+1, end);
return small+1;
}
/*
* 交換數組的兩個元素
*/
private static void swap(int[] numbers, int a, int b) {
int temp = numbers[a];
numbers[a] = numbers[b];
numbers[b] = temp;
System.out.println("current numbers:" + //記錄交換次數
""+Arrays.toString(numbers)+"----swap times:"+(++swapTimes));
}

}