常見的排序算法如下：
性能比較如下：
一般不會要求寫太復雜的排序算法，能寫幾個簡單的排序算法即可
冒泡排序
冒泡排序思路比較簡單：
- 將序列當中的左右元素，依次比較，保證右邊的元素始終大于左邊的元素；
- （ 第一輪結束后，序列最后一個元素一定是當前序列的最大值；）
- 對序列當中剩下的n-1個元素再次執行步驟1。
- 對于長度為n的序列，一共需要執行n-1輪比較
- （利用while循環可以減少執行次數）
簡單選擇排序
在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然后在剩下的數中再找最小（或者最大）的與第2個位置的數交換，以此類推，知道第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。
快速排序
- 從數列中取出一個數作為基準數
- 分區過程，將比它大的數全放到它的右邊，小于或等于它的數全放到它的左邊
- 再對左右區間重復第二步，直到各區間只有一個數
歸并排序
假設初始序列含有n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到個長度為2或1的有序子序列，在兩兩歸并，…，如此重復，直至得到一個長度為n的有序序列為止，這種排序方法稱為2-路歸并排序
方便大家粘貼，放一下文字格式
冒泡排序
public class BubbleSort {
//交換元素順序
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//冒泡排序
public static void bubbleSort(int[] a) {
for (int i=0; i<a.length - 1; i++) {
for (int j=0; j<a.length - 1 - i; j++) {
if (a[i] > a[i + 1]) {
swap(a, i, i + 1);
}
}
}
}
public static void main(String[] args) {
int[] a = {1, 5, 2, 4, 7, 6};
bubbleSort(a);
//[1, 2, 4, 5, 6, 7]
System.out.println(Arrays.toString(a));
}
}
選擇排序
public class SelectSort {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void selectSort(int[] a) {
for (int i=0; i<a.length; i++) {
int min = a[i];
int index = i;
for (int j=i; j<a.length; j++) {
if (a[j] < min) {
min = a[j];
index = j;
}
}
if (index != i) {
swap(a, i, index);
}
}
}
public static void main(String[] args) {
int[] a = {1, 5, 2, 4, 7, 6};
selectSort(a);
//[1, 2, 4, 5, 6, 7]
System.out.println(Arrays.toString(a));
}
}
快速排序
public class QuickSort {
public static int sort(int[] a, int low, int high) {
int key = a[low];
while (low < high) {
//從high所指位置向前搜索找到第一個關鍵字小于key的記錄和key互相交換
while (low < high && a[high] >= key) {
high--;
}
a[low] = a[high];
//從low所指位置向后搜索，找到第一個關鍵字大于key的記錄和key互相交換
while (low < high && a[low] <= key) {
low++;
}
a[high] = a[low];
}
//此時low和key相等
a[low] = key;
return low;
}
public static void quickSort(int[] a, int low, int high) {
if (low < high) {
int key = sort(a, low, high);
quickSort(a, low, key - 1);
quickSort(a, key + 1, high);
}
}
public static void main(String[] args) {
int[] a = {1, 5, 2, 4, 7, 6};
quickSort(a, 0, a.length - 1);
//[1, 2, 4, 5, 6, 7]
System.out.println(Arrays.toString(a));
}
}
歸并排序
public class MergeSort {
public static void sort(int[] src) {
int[] temp = new int[src.length];
msort(src,temp,0,src.length-1);
}
public static void msort(int[] src,int[] dest,int left,int right) {
if (left < right) {
int mid = (left + right) / 2;
msort(src,dest,0,mid);
msort(src,dest,mid+1,right);
merge(src,dest,0,mid,right);
}
}
public static void merge(int[] src,int[] dest,int left,int mid,int right) {
int i = left;//左邊數組的游標
int j = mid + 1;//右邊數組的游標
int index = 0;//dest起一個中途存儲的作用，這個是dest數組的游標
while (i <= mid && j <= right) {
if (src[i] <= src[j]) {
dest[index++] = src[i++];
} else {
dest[index++] = src[j++];
}
}
//復制左邊剩余的數組
while (i <= mid) {
dest[index++] = src[i++];
}
//復制右邊剩余的數組
while (j <= right) {
dest[index++] = src[j++];
}
index = 0;
while (left <= right) {
src[left++] = dest[index++];
}
}
public static void main(String[] args) {
int[] arr = {7,5,3,4,2,1,6,2,9,8};
sort(arr);
//[1, 2, 2, 3, 4, 5, 6, 7, 8, 9]
System.out.println(Arrays.toString(arr));
}
}
