冒泡、插入、归并、堆排序、快速排序的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;
}