排序-基础
一 冒泡排序
- 平均时间复杂度：O(N^2)
- 最佳时间复杂度：O(N)
- 最差时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定
// 冒泡排序 class BubbleSort{ public LinkedList<Integer> Sort(LinkedList<Integer> list,int len) { Integer flag; for (int i = 0; i < len; i++){ for (int j = 1; j < len - i; j++){ if (list.get(j - 1) > list.get(j)){ flag = list.get(j - 1); list.set(j - 1,list.get(j)); list.set(j,flag); } } } return list; } } 二 插入排序
- 平均时间复杂度：O(N^2)
- 最差时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定
// 插入排序 class InsertSort{ public LinkedList<Integer> Sort(LinkedList<Integer> list,int len) { for (int i = 1; i < len; i++){ Integer flag = list.get(i); int j; for (j = i - 1; j >= 0; j--){ if (list.get(j) > flag){ list.set(j+1,list.get(j)); }else{ break; } } list.set(j+1,flag); } return list; } } 三 希尔排序
- 平均时间复杂度：O(Nlog2N)
- 最佳时间复杂度：
- 最差时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 复杂性：较复杂
// 希尔排序 class ShellSort { public LinkedList<Integer> Sort(LinkedList<Integer> list,int len) { int gap = len, i, j; int temp; for (; gap > 0; gap /= 2){ for (i = gap; i < len; i++) { temp = list.get(i); for (j = i - gap; j >= 0 && list.get(j) > temp; j -= gap){ list.set(j + gap,list.get(j)); } list.set(j + gap,temp); } } return list; } } 四 选择排序
- 平均时间复杂度：O(N^2)
- 最佳时间复杂度：O(N^2)
- 最差时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：不稳定
// 选择排序 class SelectionSort { public LinkedList<Integer> Sort(LinkedList<Integer> list, int len) { Integer flag,min; for (int i = 0; i < len - 1; i++) { flag = i; min = list.get(i); for (int j = i + 1; j < len; j++){ if (list.get(j) < min){ flag = j; min = list.get(j); } } list.set(flag,list.get(i)); list.set(i,min); } return list; } } 五 快速排序
平均时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的不同而不同