# 比较排序算法的下届

$$n! \leq l \leq {2}^{n}$$

\begin{align} h \geq \lg(n!) = \Omega(n\lg n) \end{align}

# 计数排序(Counting-Sort)

void counting_sort(int A[], int B[], int k) {
int C[k+1];

for (int i = 0; i <= k; i++) {
C[i] = 0;
}

for (int j = 0; j < length(A); j++) { C[A[j]]++; }
for (int i = 1; i <= k; i++) { C[i] += C[i-1]; }

for (int j = length(A) - 1; j >= 0; j--) {
B[C[A[j]]] = A[j];
C[A[j]]--;
}
}


for (int i = 0; i <= k; i++) {
C[i] = 0;
}


for (int j = 0; j < length(A); j++) { C[A[j]]++; }


for (int i = 1; i <= k; i++) { C[i] += C[i-1]; }


for (int j = length(A) - 1; j >= 0; j--) {
B[C[A[j]]] = A[j];
C[A[j]]--;
}


for (int j = length(A) - 1; j >= 0; j--)


for (int j = 0; j < length(A); j++)


void radix_sort(int A[], int d) {
for (int i = 0; i < d; i++) {
Use a stable sort to sort array A on digit i
}
}


# 桶排序(Bucket-Sort)

void bucket_sort(int A[]) {
int n = length(A);
int B[n];

for (int i = 0; i < n; i++) {
B[i] = 0;
}

for (int i = 0; i < n; i++) {
append(B[int(n * A[i])], A[i]);
}

for (int i = 0; i < n; i++) {
insertion_sort(B[i]);
}

int j = 0;
for (int i = 0; i < n; i++) {
delete(B[i]);
j++;
}
}
}


$$T(n) = \Theta(n) + \sum_{i=0}^{n-1}{O({n}_{i}^2)}$$