排序算法种类:
冒泡 选择 插入(希尔)
快速排序 分组排序 基数排序 桶排序 堆排序 归并排序
#include <stdio.h> void print(int* a, int len, bool isBefore = true); int main() { int arr[10] = { 1,9,66,0,33,5,2,88,666,233 }; print(arr, 10); print(arr, 10, false); while (1); return 0; } void print(int* a, int len, bool isBefore) { if (isBefore) printf("before sort:"); else printf("after sort:"); for (int i = 0; i < len; i++) printf("%d", a[i]); printf("\n"); }
中间填充排序算法
思想(升序):
比较相邻的两个元素哪个比较大,若大的在后面,不管,若小的在后面交换
一轮过后,第len个数据就是最大的,
#include <stdio.h> void print(int* a, int len, bool isBefore = true); void bubble_sort(int* a, int len); int main() { int arr[10] = { 1,9,66,0,33,5,2,88,666,233 }; print(arr, 10); printf("bubble_sort\n"); bubble_sort(arr, 10); print(arr, 10, false); while (1); return 0; } //冒泡排序 void bubble_sort(int* a, int len) { int temp; for (int i = 0; i < len; i++) {//外层循环 for (int j = 0; j < len - i - 1; j++) { printf("i:%d,j:%d", i, j); if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } void print(int* a, int len, bool isBefore) { if (isBefore) printf("before sort:"); else printf("after sort:"); for (int i = 0; i < len; i++) printf("%d", a[i]); printf("\n"); }
一轮选一个最小的,下一轮继续选个最小的,9轮之后即可
#include <stdio.h> void select_sort(int* a, int len); void print(int* a, int len, bool isBefore = true); int main() { int arr[10] = { 1,9,66,0,33,5,2,88,666,233 }; void select_sort(arr, 10); print(arr, 10, false); while (1); return 0; } void select_sort(int* a, int len) { int temp; int minidx; for (int i = 0; i < len - 1; i++) { temp = a[i]; minidx = i; for (int j = i; j < len; j++) { minidx = (a[j] < a[minidx]) ? j : minidx; } a[i] = a[minidx]; a[minidx] = temp; } } void print(int* a, int len, bool isBefore) { if (isBefore) printf("before sort:"); else printf("after sort:"); for (int i = 0; i < len; i++) printf("%d", a[i]); printf("\n"); }
先假设数组有序,每次往有序数组中插入一个
#include <stdio.h> #include <algorithm> void print(int* a, int len, bool isBefore = true); void insert_sort(int* a, int len); int main() { int arr[10] = { 1,9,66,0,33,5,2,88,666,233 }; printf("insert_sort\n"); insert_sort(arr, 10); print(arr, 10, false); while (1); return 0; } void insert_sort(int* a, int len) { int temp; int j; for (int i = 1; i < len; i++) { temp = a[i]; j = i - 1; while (j >= 0 && a[j] > temp) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; print(a, 10); } } void print(int* a, int len, bool isBefore) { if (isBefore) printf("before sort:"); else printf("after sort:"); for (int i = 0; i < len; i++) printf("%d", a[i]); printf("\n"); }
引入步长概念,每次按照步长分组,组内做插入排序
步长每次变化,通常折半
#include <stdio.h> void print(int* a, int len, bool isBefore = true); void shell_sort(int* a, int len); int main() { int arr[10] = { 1,9,66,0,33,5,2,88,666,233 }; shell_sort(arr, 10); print(arr, 10, false); while (1); return 0; } void shell_sort(int* a, int len) { int step = len / 2; int temp = 0; int j; while (step) { for (int i = temp; i < len; i++) { temp = a[i]; j = i - step; while (j >= 0 && a[j] > temp) { a[j + 1] = a[j]; j--; } a[j + step] = temp; print(a, 10); } step = step / 2; } } void print(int* a, int len, bool isBefore) { if (isBefore) printf("before sort:"); else printf("after sort:"); for (int i = 0; i < len; i++) printf("%d", a[i]); printf("\n"); }