1、冒泡排序public class SortAlgorithm {
//1、冒泡排序bubbleSort
public static void bubbleSort(int[] num){
int len = num.length;
for(int i =len-1; i>0;i--){
for(int j=0; j<=i-1;j++){
if(num[j]>num[j+1]){
swap(num,j,j+1);
}
}
}
}
public static void swap(int[] a,int i,int j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
3、插入排序public static void insertSort(int[] arr){
int temp;
int len = arr.length;
for(int i = 1; i
int j=i-1;
temp = arr[i];
while(j>=0){
if(arr[j]>temp){
arr[j+1] = arr[j];
j--;
}
else{
break;
}
}
j++;
arr[j] = temp;
}
}
4、堆排序public static void heapSort(int[] arr){
int len = arr.length;
for(int parent = (len-1)/2; parent>=0;parent--){
adjustHeap(arr,parent,len);
}
int lastLeaf = len-1;
while(lastLeaf>=1){
// System.out.println("lastLeaf:" + lastLeaf);
swap(arr,0,lastLeaf);
adjustHeap(arr,0,lastLeaf);
lastLeaf--;
}
}
public static void adjustHeap(int[] arr, int parent,int len){
// int len = arr.length;
while((parent*2+1)
int left = parent*2+1;
if(parent*2+2
int right = parent*2+2;
if(arr[left]
swap(arr,left,right);
}
}
//System.out.println(left);
if(arr[parent]
swap(arr,left,parent);
}
parent = parent*2+1;
}
}
public static void swap(int[] a,int i,int j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
5、歸并排序public static void mergeSort(int[] arr){
sort(arr,0,arr.length-1);
}
public static void sort(int[] arr, int begin, int end){
if(begin>=end){
return;
}
int meddle = (begin+end)/2;
sort(arr,begin,meddle);
sort(arr,meddle+1,end);
merge(arr,begin,meddle,end);
}
public static void merge(int[] arr, int begin, int meddle, int end){
int[] newArr = new int[end-begin+1];
//從begin到meddle，和meddle+1到end中，把小的數放進newArr中
int newIndex=0;
int i=begin;
int j = meddle+1;
while(i<=meddle && j<=end){
if(arr[i]>arr[j]){
newArr[newIndex++] = arr[j++];
}
else{
newArr[newIndex++] = arr[i++];
}
}
while(i<=meddle){
newArr[newIndex++] = arr[i++];
}
while(j<=end){
newArr[newIndex++] = arr[j++];
}
//更新把排序好的newArr更新到arr對應的位置中
for(int k = begin;k<=end;k++){
arr[k] = newArr[k-begin];
}
}
6、快速排序
public static void qsort(int[] arr){
if(arr == null || arr.length <=1 ){
return;
}
partition(arr,0,arr.length-1);
}
public static void partition(int[] arr, int begin, int end){
if(arr == null || begin>=end){
return;
}
int small = begin-1;
for(int index = begin; index
if(arr[index]
small++;
//System.out.println(small);
if(index != small){
swap(arr,index,small);
}
}
}
small++;
swap(arr,small,end);
partition(arr,begin,small-1);
partition(arr,small+1,end);
}
public static void swap(int[] a,int i,int j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
2、選擇排序public static void selectSort(int[] arr){
int len = arr.length;
for(int i =0; i
int minIndex = i;
for(int j = i;j
if(arr[j]
minIndex = j;
}
}
swap(arr,i,minIndex);
}
}
public static void swap(int[] a,int i,int j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
各個算法的時間複雜度和空間複雜度以及穩定性：
