总结点排序的基础知识。
#插入排序 ##Straight Insertion Sort 直接插入排序的基本思想是：把待排数组看成一个有序表和一个无序表，有序表的元素个数初始为1，即为$a[0]$，经过$n-1$次插入后，无序表成为空表，排序完成。记得当初算法课教材上用的是理牌的图，非常形象。
内外两次遍历，时间复杂度为$O(n^2)$。
//左闭右开区间
typedef int elem_t;
void straight_insertion_sort (elem_t a[], const int start, const int end) {
elem_t tmp;
int i, j;
for (i = start + 1; i < end; i++) {
tmp = a[i];
for (j = i - 1; tmp < a[j] && j >= start; j--) {
a[j + 1] = a[j];
}
a[j + 1] = tmp;
}
}void InsertSort(dataList<T>& L, const int left, const int right) {
Element<T> temp;
int i, j;
for (i = left+1; i <= right; i ++) {
if (L[i] < L[i-1]) {
temp = L[i];
j = i-1;
do {
L[j+1] = L[j];
j --;
} while (j >= left && temp < L[j]);
L[j+1] = temp;
}
}
};def insert_sort(lists):
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists##Binary Insertion Sort 折半插入排序就是用折半查找插入位置。故时间复杂度为$O(n\log n)$。
void binary_insertion_sort (elem_t a[], const int start, const int end) {
elem_t tmp;
int i, j, left, right, mid;
for (i = start + 1; i < end; i++) {
tmp = a[i];
left = start;
right = i - 1;
while (left <= right) {
mid = (left + right) / 2;
if (tmp < a[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (j = i - 1; j >= left; j--) {
a[j + 1] = a[j];
}
a[left] = tmp;
}
}template <class T>
void BinaryInsertSort(dataList<T>& L, const int left, const int right) {
Element<T> temp;
int i, low, high, middle, k;
for (i = left+1; i <= right; i ++) {
temp = L[i];
low = left;
high = i-1;
while (low <= high) {
middle = (low + high) / 2;
if (temp < L[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
for (k = i-1; k >= low; k --) {
L[k+1] = L[k];
}
L[low] = temp;
}
};##Shell Sort 希尔排序是将元素分配到gap个子序列中各自进行插入排序，然后不断缩小gap的值，当gap为1时，排序完成。
初始gap值为$\lfloor\frac{n}{3}\rfloor+1$，以后每次gap取$\lfloor\frac{gap}{3}\rfloor+1$，直到1.
static void shell_insert (elem_t a[], const int start, const int end, const int gap) {
elem_t tmp;
int i, j;
for (i = start + gap; i < end; i ++) {
tmp = a[i];
for (j = i - gap; tmp < a[j] && j >= start; j -= gap) {
a[j + gap] = a[j];
}
a[j + gap] = tmp;
}
}
void shell_sort (elem_t a[], const int start, const int end) {
int gap = end - start;
while (gap > 1) {
gap = gap / 3 + 1;
shell_insert(a, start, end, gap);
}
}template <class T>
void ShellSort(dataList<T>& L, const int left, const int right) {
int i, j, gap = right-left+1;
Element<T> temp;
do {
gap = gap/3+1;
for (i = left+gap; i<= right; i ++) {
if (L[i] < L[i-gap]) {
temp = L[i];
j = i-gap;
do {
L[j+gap] = L[j];
j = j-gap;
} while (j > left && temp < L[j]);
L[j+gap] = temp;
}
}
} while (gap > 1);
};def shell_sort(lists):
count = len(lists)
step = 2
group = count / step
while group > 0:
for i in range(0, group):
j = i + group
while j < count:
k = j - group
key = lists[j]
while k >= 0:
if lists[k] > key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return lists#交换排序 ##Bubble Sort 冒泡排序：每次将最小元素冒到第一个位置，下一轮就不用继续冒泡了。最多$n-1$趟冒泡就完全排好。
基本冒泡。
void BubbleSort(T V[], int n) {
for (int i = 1; i < n; i ++) {
for (int j = n - 1; j >= i; j --) {
if (V[j-1] > v[j]) {
T temp = V[j-1];
V[j-1] = V[j];
V[j] = temp;
}
}
}
};def bubble_sort(lists):
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
temp = lists[j]
lists[j] = lists[i]
lists[i] = temp
return lists 改进版。用exchange标识本趟冒泡是否发生了逆序和交换。若没有则表示全部元素已经拍好序。
typedef int elem_t;
void bubble_sort (elem_t a[], const int start, const int end) {
int exchange;
elem_t tmp;
int i, j;
for (i = start; i < end - 1; i ++) {
exchange = 0;
for (j = end - 1; j > i; j --) {
if (a[j - 1] > a[j]) {
tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
exchange = 1;
}
}
if (exchange == 0) return;
}
}void BubbleSort(T V[], int n) {
bool exchange;
int i, j;
for (i = 1; i < n; i ++) {
exchange = false;
for (j = n-1; j >= i; j --) {
if (V[j-1] > V[j]) {
T temp = V[j-1];
V[j-1] = V[j];
V[j] = temp;
exchange = true;
}
}
if (exchange == false) {
return;
}
}
};##Quick Sort 快速排序思想：任取某元素作标准，按大小将其它元素分列左右，再对子列重复此算法。整个过程可递归。
typedef int elem_t;
int partition (elem_t a[], const int start, const int end) {
int i = start;
int j = end - 1;
const elem_t pivot = a[i];
while (i < j) {
while (i < j && a[j] >= pivot) j --;
a[i] = a[j];
while (i < j && a[i] >= pivot) i ++;
a[j] = a[i];
}
a[i] = pivot;
return i;
}
void quick_sort (elem_t a[], const int start, const int end) {
if (start < end - 1) {
const int pivot_pos = partition (a, start, end);
quick_sort(a, start, pivot_pos);
quick_sort(a, pivot_pos + 1, end);
}
}template <class T>
void QuickSort(dataList<T>& L, const int left, const int right) {
if (left < right) {
int pivotpos = L.Partitio(left, right);
QuickSort(L, left, pivotpos - 1);
QuickSort(L, pivotpos + 1, right);
}
};
template <class T>
int dataList<T>::Partition(const int low, const int high) {
int pivotpos = low;
Element<T> pivot = Vector[low];
for (int i = low+1; i <= high; i ++) {
if (Vector[i] < pivot) {
pivotpos ++;
if (pivotpos != i) {
Swap(Vector[pivotpos], Vector[i]);
}
}
}
Vector[low] = Vector[pivotpos];
Vector[pivotpos] = pivot;
return pivotpos;
};def quick_sort(lists, left, right):
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists改进版。在递归调用过程，当待排序的子序列规模小于预先确定的M时，程序调用直接插入排序算法对此子序列进行排序。
template <class T>
void QuickSort_insert(dataList<T>& L, const int left, const int right) {
if (right - left <= M) {
InsertSort(L, left, right);
} else {
int pivotpos = L.Partition(left, right);
QuickSort(L, left, pivotpos-1);
QuickSort(L, pivotpos+1, right);
}
};#直接选择排序
def select_sort(lists):
count = len(lists)
for i in range(0, count):
min = i
for j in range(i + 1, count):
if lists[min] > lists[j]:
min = j
temp = lists[min]
lists[min] = lists[i]
lists[i] = temp
return lists#堆排序
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i < size / 2:
if lchild < size and lists[lchild] > lists[max]:
max = lchild
if rchild < size and lists[rchild] > lists[max]:
max = rchild
if max != i:
list[max], lists[i] = lists[x], lists[max]
adjust_heap(lists, max, size)
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)#归并排序
def merge(left, right):
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
if len(lists) <= 1:
return lists
num = len(lists) / 2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)#基数排序
import math
def radix_sort(lists, radix = 10):
k = int(math.ceil(math.log(max(lists), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, k + 1):
for j in lists:
bucket[j / (radix ** (i - 1)) % (radix ** i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists