[TOC]

算法分类

不稳定排序算法

  1. 选择排序 — O(n²)
  2. 希尔排序 — O(nlogn)
  3. 堆排序 — O(nlogn)
  4. 快速排序 — O(nlogn) 期望时间,O(n²) 最坏情况;

稳定排序算法

  1. 冒泡排序 — O(n²)
  2. 插入排序 — O(n²)
  3. 桶排序 — O(n); 需要 O(k)额外空间
  4. 计数排序 — O(n+k); 需要O(n+k) 额外空间
  5. 合并排序 — O(nlogn); 需要O(n) 额外空间
  6. 二叉排序树排序 —O(n log n) 期望时间; O(n²)最坏时间; 需要O(n) 额外空间
  7. 基数排序 —O(n·k); 需要O(n) 额外空间

快排code

public static int[] qSort(int[] arr, int s, int e) {
int p = arr[s], i = s, j = e;
while (i<j) {
while ((i<j)&&(arr[j]>p)) {
j--;
}
while ((i<j)&&(arr[i]<p)) {
i++;
}
if ((arr[i]==arr[j])&&(i<j)) {
i++;
} else {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (s<i-1) arr=qSort(arr,s,i-1);
if (j+1<e) arr=qSort(arr,j+1,e);
return (arr);
}

public static void main(String[] args) {
int[] arr = new int[]{1,3,8,2,5,4,9,0};
arr=qSort(arr,0,arr.length-1);
for (int i:arr) {
System.out.print(i+" ");
}
}