排序
Opened this issue · 1 comments
thyecust commented
选择排序
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void SelectSort(int A[], int N) {
int i,j,k;
for (i = 0; i < N - 1; i++) {
k = i;
for (j = i + 1; j < N; j++){
if (A[j] < A[k]) {
k = j;
}
}
swap(&A[i], &A[k]);
}
}
void show(int A[], int N) {
int i;
for (i = 0; i < N; i++) {
std::cout << A[i] << " ";
}
std::cout << endl;
}
int main() {
int A[5] = {1,3,2,4,5};
SelectSort(A, 5);
show(A, 5);
}
考虑 2,2,1
,可见选择排序是不稳定的。
时间复杂度是 O(n^2),空间复杂度 O(1)。
插入排序
void InsertSort(int A[], int N) {
int p, i;
int ap;
for (p = 1; p < N; p++) {
ap = A[p];
for (i = p; i > 0 && A[i-1] > ap; i--){
A[i] = A[i-1];
}
A[i] = ap;
show(A, N);
}
}
int main() {
int A[6] = {5,4,3,7,2,1};
InsertSort(A, 6);
}
输出:
4 5 3 7 2 1
3 4 5 7 2 1
3 4 5 7 2 1
2 3 4 5 7 1
1 2 3 4 5 7
是稳定排序。
希尔排序
void ShellSort(int A[], int N) {
int si, d, p, i;
int tmp;
int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
for (si = 0; Sedgewick[si] < N; si++);
for (d = Sedgewick[si]; d > 0; d = Sedgewick[++si]) {
for (p = d; p < N; p++) {
tmp = A[p];
for (i = p; i >= d && A[i-d] > tmp; i -= d) {
A[i] = A[i-d];
}
A[i] = tmp;
show(A, N);
}
}
}
冒泡排序
void BubbleSort(int A[], int N) {
int p, i;
bool flag;
for (p = N - 1; p >= 0; p--) {
flag = true;
for (i = 0; i < p; i++) {
if (A[i] > A[i+1]) {
swap(&A[i], &A[i+1]);
flag = false;
}
}
show(A, N);
if (flag) break;
}
}
thyecust commented
快速排序
def InsertSort(arr: list):
isorted = 1
while isorted < len(arr):
tmp = arr[isorted]
i = isorted - 1
while i >= 0 and tmp < arr[i]:
arr[i + 1] = arr[i]
i -= 1
arr[i+1] = tmp
isorted += 1
def Isort(arr: list, left: int, right: int):
a = arr[left:right+1]
InsertSort(a)
arr[left:right+1] = a
def median3(arr: list, left: int, right: int):
center = (left + right) // 2
# make arr[left] <= arr[center] <= arr[right]
if arr[left] > arr[center]:
arr[left],arr[center] = arr[center],arr[left]
if arr[center] > arr[right]:
arr[center],arr[right] = arr[right],arr[center]
if arr[left] > arr[right]:
arr[left],arr[right] = arr[right],arr[center]
# move arr[center] to right end
arr[center],arr[right] = arr[right],arr[center]
return arr[right]
def Qsort(arr: list, left: int, right: int):
if right - left > 5:
pivot = median3(arr, left, right)
lo, hi = left, right - 1
while True:
if arr[lo] < pivot:
lo += 1
if arr[hi] > pivot:
hi -= 1
if lo < hi:
arr[lo], arr[hi] = arr[hi], arr[lo]
else:
arr[lo], arr[-1] = arr[-1], arr[lo]
break
Qsort(arr, left, hi)
Qsort(arr, hi, right)
else:
Isort(arr, left, right)
def QuickSort(arr: list):
Qsort(arr, 0, len(arr) - 1)
if __name__ == "__main__":
arr = [35,12,7,36,43,44,94,59,85,52,62,8,11,3,4,5,2]
QuickSort(arr)
print(arr)