前言
参考:
白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇 <编程珠玑> <C程序设计语言>
冒泡排序
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
#include "pch.h"
#include <iostream>
using namespace std;
void BubbleSort(int a[], int n)
{
int i, j;
i = j = 0;
for (i = 0; i < n; i++)
{
for (j = 1; j < n - i; j++)
{
if (a[j] < a[j - 1]) //升序
swap(a[j], a[j - 1]);
}
}
}
void BubbleSort2(int a[], int n)
{
int i,j,f,k;
i = j = f = k = 0;
f = n;
while(f > 0)
{
k = f;
f = 0;
for (j = 1; j < k; j++)
{
if (a[j] < a[j - 1]) //升序
{
swap(a[j], a[j - 1]);
f = j;
}
}
}
}
int main()
{
int a[] = {4,5,1,2,9,45,4225,11,452,4,254,14,1,454,555,4,26};
int n = sizeof(a) / sizeof(int);
cout << "Old: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
BubbleSort2(a, n);
cout << "New: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}结果:
Old:
4 5 1 2 9 45 4225 11 452 4 254 14 1 454 555 4 26
New:
1 1 2 4 4 4 5 9 11 14 26 45 254 452 454 555 4225总结:
冒泡排序比较基本,效率很差,很少有人用.纯是初学者拿来玩.
BubbleSort:
for(记录冒泡最顶端的数n-i)
for(两两交换,将一趟中最大的数移动到顶端n-i)
BubbleSort2:
while(flag记录当前冒泡顶端的位置,以及判断本趟有没有有效移动,可以提前结束)
for(一趟比较和移动,终点是上次移动的顶端k/f,跳过右边本来有序的情况)插入排序
大多数纸牌游戏都采用插入排序来让玩家手上的牌有序,当拿到一张新牌时,将其插入到合适的位置
#include "pch.h"
#include <iostream>
using namespace std;
void InsertSort(int a[], int n)
{
int i, j, t;
i = j = t = 0;
for (i = 1; i < n; i++)
{
t = a[i];
for (j = i - 1; j >=0 && a[j] > t; j-- ) //升序
{
a[j + 1] = a[j];
}
a[j + 1] = t;
}
}
void InsertSort2(int a[], int n)
{
int i = 0;
int j = 0;
for (i = 1; i < n; i++)
{
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) //升序
{
swap(a[j], a[j + 1]);
}
}
}
int main()
{
int a[] = {4,5,1,2,9,45,4225,11,452,4,254,14,1,454,555,4,26};
int n = sizeof(a) / sizeof(int);
cout << "Old: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
InsertSort2(a, n);
cout << "New: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}结果:
Old:
4 5 1 2 9 45 4225 11 452 4 254 14 1 454 555 4 26
New:
1 1 2 4 4 4 5 9 11 14 26 45 254 452 454 555 4225
Process returned 0 (0x0) execution time : 0.024 s
Press any key to continue.总结：
左边是一个有序数组,从a[0]开始到a[n - 1]
for(将a[1...n-1]插入a[0])
for(插入a[i]需要进行的交换(挪位)操作)
InsertSort:将左边的依次右移,最后把a[i]放到合适的位置
InsertSort2:从右边开始,把乱序的左右两个数交换,直到整体有序.有点像是冒泡排序其中的一点思路.选择排序
直接选择排序和直接插入排序很相似:
直接选择排序是把无序区的最小值挪到有序区的最右边(升序)，无序区从j=1开始,有序区初始是a[0]
直接插入排序是把无序区的第一个值挪到有序区的合适位置,无序区从j=1开始,有序区初始是a[0]
#include "pch.h"
#include <iostream>
using namespace std;
void SelectSort(int a[], int n)
{
int i, j, nMinIndex;
i = j = nMinIndex = 0;
for (i = 0; i < n; i++)
{
nMinIndex = i;
for (j = i+1; j < n; j++)
{
if (a[j] < a[nMinIndex]) //升序
nMinIndex = j;
}
swap(a[i], a[nMinIndex]);
}
}
int main()
{
int a[] = {4,5,1,2,9,45,4225,11,452,4,254,14,1,454,555,4,26};
int n = sizeof(a) / sizeof(int);
cout << "Old: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
SelectSort(a, n);
cout << "New: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}结果:
Old:
4 5 1 2 9 45 4225 11 452 4 254 14 1 454 555 4 26
New:
1 1 2 4 4 4 5 9 11 14 26 45 254 452 454 555 4225shell(希尔)排序
wikipedia:
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
#include "pch.h"
#include <iostream>
using namespace std;
void ShellSort(int a[], int n)
{
int i, j, gap;
i = j = gap = 0;
int t = 0;
for (gap = n / 2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
{
swap(a[j], a[j + gap]);
}
}
}
}
void ShellSort2(int a[], int n)
{
int i, j, gap, t;
i = j = gap = t = 0;
for (gap = n / 2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
t = a[i];
for (j = i - gap; j >= 0 && a[j] > t; j -= gap)
{
a[j + gap] = a[j];
}
a[j + gap] = t;
}
}
}
int main()
{
int a[] = {4,5,1,2,9,45,4225,11,452,4,254,14,1,454,555,4,26};
int n = sizeof(a) / sizeof(int);
cout << "Old: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
ShellSort2(a, n);
cout << "New: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}总结:
理解插入排序是理解希尔排序的关键.gap = 1的时候就是完全的插入排序,gap != 1的时候,是为了让总体有序,提高插入排序的效率.因为插入排序在总体有序的情况下,效率比较高.步长(gap)一般是取一半,这并不是最优的方案.暂不深入研究.
快速排序
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列
#include "pch.h"
#include <iostream>
using namespace std;
void QuickSort(int a[], int left, int right)
{
int i, middle;
i = middle = 0;
if (left >= right)
return;
middle = left;
for (i = left + 1; i <= right; i++)
{
if (a[i] < a[left])
{
swap(a[++middle], a[i]);
}
}
swap(a[left], a[middle]);
QuickSort(a, left, middle - 1);
QuickSort(a, middle + 1, right);
}
int main()
{
int a[] = {4,5,1,2,9,45,4225,11,452,4,254,14,1,454,555,4,26};
int n = sizeof(a) / sizeof(int);
cout << "Old: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
QuickSort(a, 0, n - 1);
cout << "New: " << endl;
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}总结:
快排有很多的版本,网上很多人实现的代码比较复杂,不利于理解.效率也不好说,更重要的是很难论证是否正确,快排使用递归函数,有的时候很难简单的判断是否有误.上面记录的实现方式,是在两本书中都出现过的,一种简单的快速排序.就记住这一种吧.
理解这个的难点是middle的变化.
归并排序
堆排序
ending
