该文章所有代码均基于SortView类,头文件及基本代码如下
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class SortView {
public:
void BubbleSort();//冒泡排序
void SelectionSort();//选择排序
void InsertionSort();//插入排序
void ShellSort();//希尔排序
void Quicksort(int low, int high);//快速排序
void MergeSort(int left, int right);//归并排序
void Merge(int left, int right,int mid);//归并排序
void RadixSort();//基数排序
void Init(int n);//初始化数组
void Show();//打印数组
int Size();
private:
vector<int> Unsort;
int temp[];
};
void SortView::Init(int n) {
for (int i = 0; i < n; i++) {
Unsort.push_back(rand());
}
}
void SortView::Show() {
for (int i = 0; i < Unsort.size(); i++) {
cout << Unsort[i] <<" ";
}
cout << endl;
}
int SortView::Size() {
return Unsort.size();
}
1、冒泡排序(BubbleSort)
冒泡排序是一种较为简单的排序算法,其基本思想就是循环遍历需要排序的元素,依次比较两个相邻的元素,如果它们之间的顺序不符合需要的顺序,即将他们进行交换,知道某一次循环遍历没有需要交换的元素,排序完成。
void SortView::BubbleSort() {
int n = Unsort.size()-1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-i; j++) {
if (Unsort[j] > Unsort[j + 1]) {
swap(Unsort[j], Unsort[j + 1]);
}
}
}
return;
}
2、快速排序(Quicksort)
相对于冒泡排序来说,快速排序要比其快将近一倍的时间,具体实现的基本思想就是找一个基准元素(我选取的基准元素每次都是第一个元素)然后将基准元素和后面的元素进行比较,将所有比基准元素小的放到基准元素的左边,所有比基准元素大的放到基准元素的右边,递归进行调用自身,完成左右两边,就完成了排序。
void SortView::Quicksort(int low,int high) {
int UNhigh = high;
int corrent = low;//该变量记录当前基准元素
if (low > high)return;
for (high; high > 0; high--) {
if (Unsort[high] < Unsort[corrent]) {
for (low; low < high; low++) {
if (Unsort[low] > Unsort[high]) {
swap(Unsort[low], Unsort[high]);
break;
}
}
}
if (high == low) {
break;
}
}
swap(Unsort[corrent], Unsort[high]);
Quicksort(low, high-1);
Quicksort(high + 1, UNhigh);
}
3、归并排序(MergeSort)
归并排序采用了分而治之的思想,将很长的一段数字序列排序,分成很多的短序列进行排序,当然,分到数组里面只有一个元素的时候,该段序列本来就是有序的,对这子序列分别采用归并排序,将排序好的子序列合并成一个最终的排序序列,即完成了排序。归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。
void SortView::MergeSort(int left,int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeSort(left, mid);//左边归并排序,使得左子序列有序
MergeSort(mid + 1, right);//右边归并排序,使得右子序列有序
Merge(left, right, mid);
}
}
void SortView::Merge(int left, int right, int mid) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {//将子序列按顺序放入临时序列中
if (Unsort[i] <= Unsort[j]) {
temp[t++] = Unsort[i++];
}
else {
temp[t++] = Unsort[j++];
}
}
while (i <= mid) {//剩余的左序列
temp[t++] = Unsort[i++];
}
while (j <= right) {//剩余的右序列
temp[t++] = Unsort[j++];
}
t = 0;
while (left <= right) {//将临时序列放入原序列
Unsort[left++] = temp[t++];
}
}
4、选择排序(SelectionSort)
选择排序的实现较为简单,基本原理就是拿未排序的元素序列的首元素和后面序列的元素逐个比较,找出最小的与其进行位置调换当遍历完全部序列后,排序也就完成了。
void SortView::SelectionSort(){
int min;
int n = Unsort.size();
for (int i = 0; i < n; i++) {
min = i;
for (int j = i + 1; j < n; j++) {
if (Unsort[i] > Unsort[j]) {
if (Unsort[min] > Unsort[j])min = j;
}
}
swap(Unsort[min], Unsort[i]);
}
}
5、插入排序(InsertionSort)
插入排序的基本思想就是从前往后遍历数组,拿到当前位置的值后,与前一个元素进行比较,如果比前面的值小,则进行替换,循环执行,直到有元素比当前元素大,或者遍历到序列的头。当遍历完整个值序列,则全部值排序完毕。
void SortView::InsertionSort() {
int n = Unsort.size();
for (int i = 0; i < n; i++) {
for (int j = i; j > 0; j--) {
if (Unsort[j] < Unsort[j-1]) {
swap(Unsort[j], Unsort[j-1]);
}
else if (Unsort[j] > Unsort[j-1])break;
}
}
}
6、希尔排序(ShellSort)
希尔排序结合了插入排序的思想,在插入排序的思想下将比较的间距调整为了一个固定的值 (increment/3+1)在这个值还大于一的时候,循环进行插入排序,当这个值小于或者等于一了,排序完毕。
void SortView::ShellSort() {
int end = Unsort.size()-1, start = 0;
int increment = Unsort.size();//所有元素的数量
int temp{ 0 };
while (increment > 1) {
increment = increment / 3 + 1;
for (int i = start + increment; i <= end; ++i) { //对每个划分进行直接插入排序
if (Unsort[i - increment] > Unsort[i]) {
temp = Unsort[i];
int j = i - increment;
while (j >= start && Unsort[j] > temp)
{ //移动元素并寻找位置
Unsort[j + increment] = Unsort[j];
j -= increment;
}
Unsort[j + increment] = temp;
}
}
}
}
7、基数排序(RadixSort)
基数排序结合了计数排序的思想,先找到整个序列中最大的数字,拿到最高阶次,然后将整数按阶次切割成不同的数字,然后按每个阶次分别比较。具体实现是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从个位开始,依次进行一次排序。这样从个位排序一直到最高阶次排序完成以后, 待排序序列就变成一个有序序列,排序完成。
void SortView::RadixSort() {
auto max = max_element(Unsort.begin(), Unsort.end());
int exp, n = Unsort.size();
for (exp = 1; *max / exp > 0; exp *= 10) {
int i, buckets[10] = { 0 };
for (i = 0; i < n; i++)
buckets[(Unsort[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
buckets[i] += buckets[i - 1];
for (i = n - 1; i >= 0; i--)
{
temp[buckets[(Unsort[i] / exp) % 10] - 1] = Unsort[i];//把元素放到应该在的位置
buckets[(Unsort[i] / exp) % 10]--;
}
for (i = 0; i < n; i++)
Unsort[i] = temp[i];
}
}