排序算法
冒泡排序,插入排序,选择排序
冒泡,插入,选择排序是最基础的交换排序
时间复杂度
$$
O(n^2)
$$
冒泡排序:
冒泡排序是一种离线的算法
1 2 3 4 5 6 7 8 9 10
| for(int i = 0; i < n; i++){ bool tmp = 0; for(int j = 0; j < n - i; j++){ if(a[j] > a[j + 1]){ swap(a[j], a[j + 1]); tmp = 1; } } if(!tmp) break; }
|
插入排序:
插入排序是一种在线的算法
1 2 3 4 5 6 7 8 9
| void insert(int arr[], key) { int key = arr[len]; while(len > 1 && arr[len - 1] > key){ arr[len] = arr[len - 1]; len--; } arr[len] = key; }
|
选择排序:
1 2 3 4 5 6 7 8 9 10 11
| for(int i = 0; i < n - 1; i++){ int tmp = arr[i]; int mx = i; for(int j = i + 1; j < n; j++){ if(tmp > arr[i]){ tmp = arr[i]; mx = j; } } if(mx != i) swap(arr[i], arr[mx]); }
|
桶排序
桶排序是排序算法的一种,适用于待排序数据值域较小的情况
1 2 3 4 5 6 7 8
| int bucket[110]; for(int i = 1; i <= n; i++){ bucket[a[i]]++; } for(int i = 0; i <= 100; i++){ if(bucket[i] == 0) continue; while(bucket[i]--) cout << i << " "; }
|
快速排序
1 2 3 4 5
| void qsort(int l, int r) { int i = l, j = r; int piovt; }
|
归并排序
堆排序