算法-排序
一、冒泡排序
进行 N 趟循环，每趟循环进行相邻两数比较，根据排序的规则交换位置，每趟完成后将极值移至有序区。
时间复杂度：O(N^2)
#include<iostream>
using namespace std;
void bubble_sort(int a[], int size) {
for (int i = 0; i<size; i++) {
int flag = 0;
for (int j = 0; j<size-i; j++) {
if (a[j]>a[j+1]) {
int tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
flag++;
}
}
if (flag == 0) {
break;;
}
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
bubble_sort(a,n);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
二、选择排序
进行 i(0~N-1) 趟循环，每一趟循环将最小的数放到第i个位置，形成有序区。
时间复杂度：O(N^2)
#include<iostream>
using namespace std;
void select_sort(int a[], int size) {
for (int i = 0; i < size-1; i++) {
int min_num = i+1;
for(int j = i; j < size; j++) {
if (a[j] < a[min_num]) {
min_num = j;
}
}
int tmp = a[i];
a[i] = a[min_num];
a[min_num] = tmp;
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
select_sort(a,n);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
三、插入排序
进行 i(0~N-1) 趟循环，每一趟循环将第 i 个位置的数与之前的数进行比较，并排到符合条件的位置，形成有序区。
时间复杂度：O(N^2)
#include<iostream>
using namespace std;
void insertion_sort(int a[], int size) {
for (int i = 1; i < size; i++) {
for (int j = i-1; j>=0; j--) {
int tmp = a[j+1];
if (a[j+1] < a[j]) {
a[j+1] = a[j];
a[j] = tmp;
}
}
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
insertion_sort(a,n);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
四、快速排序
对于数组选取第一个元素，通过归位将其放入特定位置，然后以该位置为边界将列表分为两部分，递归调用快速排序。
时间复杂度：O(NlogN)， 最坏情况下是 O(N^2)
#include<iostream>
using namespace std;
int oh_partition(int a[], int left, int right) {
int tmp = a[left];
while (left < right) {
while (a[right] >= tmp && left < right) {
right --;
}
a[left] = a[right];
while (a[left] <= tmp && left < right) {
left ++;
}
a[right] = a[left];
}
a[left] = tmp;
return left;
}
void quick_sort(int a[], int left, int right) {
if (left < right) {
int mid = oh_partition(a, left, right);
quick_sort(a, left, mid-1);
quick_sort(a, mid+1, right);
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
quick_sort(a, 0, n-1);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
五、堆排序
二叉堆：近似完全二叉树。
父节点与左子节点的下标关系 i --> 2*i+1；
父节点与右子节点的下标关系 i --> 2*i+2；
大根堆：子节点大于等于父节点，堆中的最大值处于根节点；
小根堆：子节点小于等于父节点，堆中的最小值处于根节点；
推排序算法使用的是大根堆。
1、将数组维护成大根堆的形式
2、交换根节点与最后叶子节点的值，将最后的叶子节点屏蔽在后续的操作，即指定前一位节点为最后的叶子节点
3、继续维护成大根堆直至堆顶
时间复杂度：O(NlogN)
#include<iostream>
using namespace std;
void heapify(int a[], int root, int last) {
int i = root;
int tmp = a[root];
// j 指向左子节点
int j = i*2+1;
// 条件：只要 j 有值
while(j <= last) {
// 右子节点存在且右子节点大于左子节点
if (a[j+1] > a[j] && j + 1 < last) {
j+=1;// j 指向右子节点
}
if(a[j] > tmp) {
a[i] = a[j];
i = j;//向下一层
j = i*2+1;
} else {
break;
}
}
a[i] = tmp;// 把提出来的tmp 放到空的节点中
}
void heap_sort(int a[], int size) {
//从最低叶子节点的父节点开始
for (int i = size/2 - 1; i >=0; i--) {
heapify(a, i, size - 1);//维护成最大堆
}
for (int i = size - 1; i >= 0; i--) {
//交换根节点的值
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
//同时将最后的叶子节点减1，然后维护成最大堆
heapify(a, 0, i-1);
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
heap_sort(a, n);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
六、归并排序
分解待排序的 n 个元素的序列成 n/2 个元素的子序列。
递归排序子序列，合并已排序的子序列以产生整体排序序列。
时间复杂度：O(NlogN)
#include<iostream>
using namespace std;
void oh_merge(int a[], int left, int mid, int right) {
int len1 = mid - left + 1;
int len2 = right - mid;
int L[len1+1];
int R[len2+1];
for (int i = 0; i < len1; i++) {
L[i] = a[left+i];
}
L[len1] = INT_MAX;
for (int i = 0; i < len2; i++) {
R[i] = a[mid+i+1];
}
R[len2] = INT_MAX;
int i = 0;
int j = 0;
int k = left;
while (k <= right) {
if (L[i] <= R[j]) {
a[k] = L[i];
i++;
} else {
a[k] = R[j];
j++;
}
k++;
}
}
void merge_sort(int a[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(a, left, mid);
merge_sort(a, mid+1, right);
oh_merge(a, left, mid, right);
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
merge_sort(a, 0, n-1);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
七、希尔排序
将序列分为 d = n/2 组,每组的元素为原序列中间隔为 d 的元素。对每组元素进行插入排序。然后将序列分为 d = d/2 组，对每组元素进行插入排序。直到 d 为 1停止。
这里的间隔参数不一定是除 2。
时间复杂度:小于等于 O(N^2)
#include<iostream>
using namespace std;
void insertion_gap(int a[], int size, int gap) {
for (int i = gap; i < size; i++) {
for (int j = i-gap; j>=0; j-=gap) {
int tmp = a[j+gap];
if (tmp < a[j]) {
a[j+gap] = a[j];
a[j] = tmp;
}
}
}
}
void shell_sort(int a[], int size) {
int d = size / 2;
while (d >= 1) {
insertion_gap(a, size, d);
d/=2;
}
}
int main() {
int n;
while (cin >> n) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
shell_sort(a, n);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
八、计数排序
假设 n 个输入元素的每一个都是在 0 到 k 区间内的一个整数。对于每一个输入元素 x，确定小于 x 的元素个数，利用这一属性，就可以将 x 放到它在输出数组的位置上。
时间复杂度：O(N)
#include<iostream>
using namespace std;
void count_sort(int a[], int b[], int size, int k) {
int c[k+1];
for (int i = 0; i <= k; i++) {
c[i] = 0;
}
for (int i = 0; i < size; i++) {
c[a[i]] += 1;
}
for (int i = 1; i <= k; i++) {
c[i] = c[i]+c[i-1];
}
for (int i = size - 1; i >= 0; i--) {
// tmp1 = a[i] 为待排序的值
// tmp2 = c[tmp1] 为待排序的值前面有多少小于等于它的元素，由此可以得到待排序的值的下标为 tmp2 - 1
// b[tmp2] = tmp1;
b[c[a[i]]-1] = a[i];
// 将 tmp2 减 1，这样后续的遍历中遇到与 tmp1 相同的值，就直接往 tmp2 上放。相同的值总是紧挨着的。
c[a[i]] -= 1;
}
}
int main() {
int n;//输入的序列长度
int k;//输入的序列中最大的值
while (cin >> n >> k) {
int a[n];
int b[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
count_sort(a, b, n, k);
for (int i = 0; i<n; i++) {
cout << b[i] << " " << endl;
}
}
return 0;
}
九、基数排序
基于位数关键字大小比较,将序列分成一定的“桶”，然后对“桶”中的数据进行排序，最后将数据回收回原序列中
时间复杂度：O(k*n)
#include<iostream>
using namespace std;
void radix_Sort(int a[], int size, int max_num) {
for (int i = 1; max_num / i > 0; i+=10) {
int buckets[size][10];
memset(buckets, 0, sizeof(buckets));
for (int j = 0; j < size; j++) {
int num = (a[j] / i) % 10;
buckets[j][num] = a[j];
}
int k = 0;
for (int j = 0; j < 10; j++) {
for (int s = 0; s < size; s++) {
if (buckets[s][j] != 0) {
a[k++] = buckets[s][j];
}
}
}
}
}
int main() {
int n;
int k;
while (cin >> n >> k) {
int a[n];
for(int i = 0; i<n; i++) {
cin >> a[i];
}
radix_Sort(a, n, k);
for (int i = 0; i<n; i++) {
cout << a[i] << " " << endl;
}
}
return 0;
}
