【紫书】算法竞赛之排序算法笔记
Vincent& 人气:1一：冒泡排序（O(n^2)）
每组每个位置的数与它后面的数比较，前面数大于后面的数就交换数值，交换n-1组。
每次每组交换的时候，都会把最大的排到后面去，就类似与在水底泡泡慢慢的向上浮出。
特性：
稳定。
动图演示：
详细解析代码：
#include<stdio.h>
int main() {
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与动图一样的数值。
int n = 15;
//冒泡排序
for(int i=0;i<n-1;i++)//代表的是要做多少组比对，为什么是n-1呢？
//因为计数从0开始而且第一个数和自身没有比对的必要性。
for(int j=0;j<n-1-i;j++)
//代表组里面的序号，因为要与后面数做比较，而最后一个数没有与之比较的（可能会越界）所以n-1
//为什么还要-i呢？
//因为每排过一遍，这一组最大值就排到后面去了，也就没必要再去比较了。
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
for (int i = 0;i < n;i++)
printf("%d ", a[i]);
return 0;
}
二、选择排序（O(n^2)）
设置两重循环，第一重循环做为比较的基准，第二重循环找它后面比它小的数，然后与之交换。
就是选择一个它后面的所有比他小的数中的最小的数进行交换，冒泡排序是固定后面的数，而选择排序是固定前面的数。
特性：
移动数据的次数已知（n-1 次）。
动图演示：
详细解析代码：
#include<stdio.h>
int main() {
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与动图一样的数值。
int n = 15;
//选择排序
for (int i = 0;i < n - 1;i++) // 代表的是要做基数数值的下标，为什么是n - 1呢？
//因为计数从0开始而且最后一个数没得数和它进行比较了。
{
int k = i;
for (int j = i + 1;j < n;j++)//找到比基数小的数中的最小数的下标
if (a[k] > a[j]) k = j;
if (k != i) {
int temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
for (int i = 0;i < n;i++)
printf("%d ", a[i]);
return 0;
}
三、插入排序（O(n^2)）
从第二个数开始，将数字抽出来与前面的数依次比较，大于它的统统向后移动一格。
也就是将抽出来的数放到它该在的位置。
特性：
在大多数元素已经有序的情况下，插入排序的工作量较小。
动图演示：
详细解析代码：
#include<stdio.h>
int main() {
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与动图一样的数值。
int n = 15;
//选择排序
for (int i = 1;i < n ;i++) // 代表的是要放回原位数数值的下标
{
int front = i- 1;//初始化前一个数的下标
int sum = a[i];//放回原位数数值
while (front >= 0 && a[front] > sum)
//防止数组越界并且前面数比后面的数大才能继续
a[front + 1] = a[front--];
//把前面数向后移动，前一个数的下标-1，，想象动图中空格的变化
//上个循环结束了，说明空格不能再变化了，将其赋值回去就好了
a[++front] = sum;
}
for (int i = 0;i < n;i++)
printf("%d ", a[i]);
return 0;
}
四、归并排序 O(nlog(2)n)
特性：
可顺便处理逆序对的问题。
动图演示：
这个算法用动图充分体现了它的思想，放在下面的是辅助数组，将每部分以两段两段的分开进行排序，分开的排好了，再进行总的排序。
详细解析代码
#include<stdio.h>
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与动图一样的数值。
int t[20];//辅助数组，中转站的意思。
void merge_sort(int l, int r) {
//如果两个数组下标相邻，就不必要再进行二分了，再分就只有一个了，无法比较了。
if (r - l > 1) {
int m = l + (r - l >> 1), i = l, j = m, k = l;
//m为分开的的这一段的中间下标，i为左边起始点，j为右边起始点，k为辅助数组起始点。
//将总的一段二分。
merge_sort(l, m);
merge_sort(m, r);
//然后再将这两段归并到一起进行排序。
while (i < m || j < r)//防止下标越界
//先放到辅助数组中的肯定是小的，所以我们只需要将两边较小的放到辅助数组中就好了。
if (j >= r || (i < m && a[i] <= a[j])) t[k++] = a[i++];
//注意下标越界问题。
else t[k++] = a[j++];//这里处理逆序对问题。
for (i = l;i < r;i++) a[i] = t[i];
}
}
int main() {
int n = 15;
merge_sort(0, n);
for (int i = 0;i < n;i++) printf("%d ", a[i]);
return 0;
}
逆序对问题 代码：
#include<stdio.h>
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与动图一样的数值。
int t[20];//辅助数组，中转站的意思。
int ans;//逆序对数量
void merge_sort(int l, int r) {
//如果两个数组下标相邻，就不必要再进行二分了，再分就只有一个了，无法比较了。
if (r - l > 1) {
int m = l + (r - l >> 1), i = l, j = m, k = l;
//m为分开的的这一段的中间下标，i为左边起始点，j为右边起始点，k为辅助数组起始点。
//将总的一段二分。
merge_sort(l, m);
merge_sort(m, r);
//然后再将这两段归并到一起进行排序。
while (i < m || j < r)//防止下标越界
//先放到辅助数组中的肯定是小的，所以我们只需要将两边较小的放到辅助数组中就好了。
if (j >= r || (i < m && a[i] <= a[j])) t[k++] = a[i++];
//注意下标越界问题。
else t[k++] = a[j++],ans+=m-i;//这里处理逆序对问题。
for (i = l;i < r;i++) a[i] = t[i];
}
}
int main() {
int n = 15;
merge_sort(0, n);
printf("%d\n", ans);
return 0;
}
只要你把
else t[k++] = a[j++];成else t[k++]=a[j++],ans+=m-i;就好了，记得声明ans变量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
而else恰好符合这个条件只要有一个是从右边的数加进来的，就说明当前（左边）下标的 i到m-1都是大于这个数的。
五、快速排序 O(nlog(2)n)
以中间数作为基数，同时从左右边开始比较，因为基数是在中间，所以左边的数要比基数小，右边的数要比基数大，否则就交换数值，分支递归反复便得出正确的顺序。
特性：
可以处理求第几大的问题;极快，数据移动少;
缺点：
不稳定。
详细解析代码：
#include<stdio.h>
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与之前一样的数值。
void quick_sort(int l, int r) {
if (l < r) {//防止越界
int i = l - 1, j = r + 1, x = a[l + r >> 1];
//-1、+1的原因是因为下面我们要用++i、--j。
//为什么不用i++、j++呢？因为我们要比较数值，要让i、j与我们比较的数值下标同步，提前+1或者-1会导致后面的交换发生错误。
//前者是先使用i+1再将i=i+1，后者是先使用i再将i=i+1。
while (i < j) {
//双指针移动不符合就暂停
while (a[++i] < x);
while (a[--j] > x);
//两边都不符合了，交换数值。
if (i < j) {//学了c++后可直接用swap函数。
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//再分治，左右两边递归排序。
quick_sort(l, j);quick_sort(j + 1, r);
}
}
int main() {
int n=15;
quick_sort(0, n - 1);
for (int i = 0;i < n;i++) printf("%d ", a[i]);
return 0;
}
寻找第k小的数 代码：
#include<stdio.h>
int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解，我将数值设为与之前一样的数值。
int quick_sort(int l, int r, int k) {
if (l == r) return a[l];
int i = l - 1, j = r + 1, x = a[l + r >> 1];
//-1、+1的原因是因为下面我们要用++i、--j。
//为什么不用i++、j++呢？因为我们要比较数值，要让i、j与我们比较的数值下标同步，提前+1或者-1会导致后面的交换发生错误。
//前者是先使用i+1再将i=i+1，后者是先使用i再将i=i+1。
while (i < j) {
//双指针移动不符合就暂停
while (a[++i] < x);
while (a[--j] > x);
//两边都不符合了，交换数值。
if (i < j) {//学了c++后可直接用swap函数。
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int s = j - l + 1;//判断左边有多少数，是否包含第k个数
//分治，不断缩小范围，直到l==r，输出答案。
if (k <= s) return quick_sort(l, j, k);
//k>s的话说明第K个值在右边的第k-s 个数中，那么在右边的k=k-s;
return quick_sort(j + 1, r, k - s);
}
int main() {
int n = 15, k = 5;
int ans = quick_sort(0, n - 1, k);
printf("%d \n", ans);
return 0;
}
加载全部内容