原因:2017年5月9日 星期二 说明:思想
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n²) | O(nlogn) | O(n²) | O(1) | 稳定 |
简单选择 | O(n²) | O(n²) | O(n²) | O(1) | 稳定 |
直接插入 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
希尔排序 | O(nlogn)~O(n²) | O(n^1.3) | O(n²) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 不稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(nlogn)~O(n) | 不稳定 |
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectSort(arr):
newArr = []
for i in range(len(arr)):
smallest_index = findSmallest(arr)
newArr.append(arr.pop(smallest_index))
return newArr
print selectSort([5,3,6,2,10])
public static void sort(Comparable[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0)
minIndex = j;
}
swap(arr, i, minIndex);
}
}
public static void sort(Comparable[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j].compareTo(arr[j-1]) < 0)
swap(arr, j, j-1);
else
break;
}
}
}
public static void sort(Comparable[] arr) {
for (int i = 1; i < arr.length; i++) {
Comparable e = arr[i];
int j;
for (j = i; j > 0 && arr[j - 1].compareTo(e) > 0; j--)
arr[j] = arr[j - 1];
arr[j] = e;
}
}
//插入元素
public void insert(Item item) {
assert count + 1 <= capacity;
data[count + 1] = item;
count++;
shiftUp(count);
}
private void shiftUp(int k) {
while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
swap(k, k / 2);
k /= 2;
}
}
public Item extractMax() {
assert count > 0;
Item ret = data[1];
swap(1, count);
count--;
shiftDown(1);
return ret;
}
private void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k; //此轮循环中data[k]与data[j]交换位置
if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0)
j++;
if (data[j].compareTo(data[k]) <= 0)
break;
swap(j, k);
k = j;
}
}
public MaxHeap(int capacity) {
data = (Item[]) new Comparable[capacity + 1];
count = 0;
this.capacity = capacity;
}
public MaxHeap(Item[] arr) {
int n = arr.length;
data = (Item[]) new Comparable[n + 1];
capacity = n;
for (int i = 0; i < n; i++)
data[i + 1] = arr[i];
count = n;
for (int i = count / 2; i >= 1; i--)
shiftDown(i);
}
(count-1)/2