1.直接插入排序。其中len的值为待排序数的长度+1，数组第一个空间用作辅助。基本思想：直接插入排序其基本操作就是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。这里就是将待排序的数插入已排序好的序列中从而实现排序。
void Sort::InsertSort() {
int i, j;
for (i = 2; i<this->len; i++) {
if (this->array[i]<this->array[i - 1]) {
this->array[0] = this->array[i];
for (j = i - 1; j > 0 && this->array[0] < this->array[j]; j--) {
this->array[j + 1] = this->array[j];
}
this->array[j + 1] = this->array[0];
}
}
}
2.折半插入排序。它的基本思想同直接插入排序，只是在寻找插入位置的方式上不同，直接插入排序是逐个比较并后移，折半插入排序是通过折半查找找到插入的位置，之后在进行后移元素操作。
void Sort::HalfInsertSort() {
int i, j, low, high,mid;
for (i = 2; i < len; i++) {
this->array[0] = this->array[i];
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (this->array[i] < this->array[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
for (j = i - 1; j >= high + 1; j--)
this->array[j + 1] = this->array[j];
this->array[high + 1] = this->array[0];
}
3.希尔排序。希尔排序也属于插入类排序，又称为缩小增量排序，他是非稳定的。该排序就是把记录按下标的一定增量分组，对每组数使用直接插入排序，当增量减至1时，待排序数正好被分为1组，也就是排序完毕，算法终止。
void Sort::ShellSort() {
int i, j;
//初始增量为总长度的一半，之后依次除2且向下取整，且最后一次要为1
for (int d = (this->len-1) / 2; d >= 1; d /= 2) {
for (i = d + 1; i < this->len; i++) {//分组
if (this->array[i] < this->array[i - d]) {
this->array[0] = this->array[i];
for (j = i - d; j > 0 && this->array[0] < this->array[j]; j -= d) {
this->array[j + d] = this->array[j];
}
this->array[j + d] = this->array[0];
}
}
}
}
4.冒泡排序。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
void Sort::BubbleSort() {
for (int i = 1; i < this->len-1; i++) {
bool flag = false;//当整个序列有序的时候，标志位不发生修改，从而表示已经排好了
for (int j = this->len - 1; j > i; j--) {
if (this->array[j] < this->array[j - 1]) {
int temp = this->array[j];
this->array[j] = this->array[j - 1];
this->array[j - 1] = temp;
flag = true;
}
}
if (flag == false) {
return;
}
}
}
5.快速排序，它是基于分治法的排序算法。分治法：第一步将原问题分割为若干个子问题，这个子问题只是原问题较小规模的实例；第二步将解决这些子问题，递归地求解这些问题，递归的边界就是问题规模足够小的时候，可以直接求解。基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
int Sort::Partition(int low, int high) {
int ptr = this->array[low];
while (low<high){
while (low<high&&this->array[high]>=ptr) {//low<high避免完全顺序的序列出现数组下溢
high--;
}
this->array[low] = this->array[high];
while (low < high&&this->array[low] <= ptr) {
low++;
}
this->array[high] = this->array[low];
}
this->array[low] = ptr;
return low;
}
void Sort::QuickSort(int low, int high) {
if (low < high) {
int ptr = Partition(low, high);
QuickSort(low, ptr - 1);
QuickSort(ptr + 1, high);
}
}
6.选择排序。每轮选择最小的数和this->array[i]进行交换，其中i代表轮数，n轮后就完成了排序。
void Sort::SelectSort() {
for (int i = 1; i < this->len-1; i++) {
int min = i;//min记录当前最小元素所在的下标，初值设为第i个
for (int j = i + 1; j < this->len; j++) {
if (this->array[j] < this->array[min])
min = j;
}
if (min != i) {
int temp = this->array[i];
this->array[i] = this->array[min];
this->array[min] = temp;
}
}
}
7.堆排序，它利用堆这种数据结构所设计的一种排序算法，本文使用的是最大堆排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆中要定义这几步操作：建最大堆（将堆中的所有数据重新排序），调整堆（将堆的末端子节点作调整，使得子节点永远小于父节点），堆排序（移除位在第一个数据的根节点，并做最大堆调整的递归运算）。
void Sort::BuildMaxHeap() {
for (int i = (this->len - 1) / 2; i > 0; i--)//len-1为第一个可能要检查的元素下标
AdjustDown(i,this->len-1);
}
void Sort::AdjustDown(int k,int len) {
this->array[0] = this->array[k];//k为需要检查的结点值
for (int i = 2 * k; i <= len; i *= 2) {//2*k为其左孩子结点
if (i < len && this->array[i] < this->array[i + 1])
i++;
if (this->array[0] >= this->array[i])
break;
else {
this->array[k] = this->array[i];
k = i;
}
}
this->array[k] = this->array[0];
}
void Sort::HeapSort() {
BuildMaxHeap();
for (int i = this->len - 1; i > 1; i--) {
int temp = this->array[i];
this->array[i] = this->array[1];
this->array[1] = temp;
AdjustDown(1, i - 1);
}
}
8.归并排序，它基于分治法。基本思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
void Sort::Merge(int low, int mid, int high) {
for (int k = 1; k <= this->len - 1; k++) {
this->B[k] = this->array[k];
}
int i, j, k;
for (i = low,j = mid + 1, k = i; i <= mid && j <= high; k++) {
if (this->B[i] <= this->B[j])
this->array[k] = this->B[i++];
else
this->array[k] = this->B[j++];
}
while (i<=mid)
{
this->array[k++] = this->B[i++];
}
while (j<=high)
{
this->array[k++] = this->B[j++];
}
}
void Sort::MergeSort(int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(low, mid);
MergeSort(mid + 1, high);
Merge(low, mid, high);
}
}
9.基数排序，又称"桶子法"，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其中r为所采取的基数，在某些时候，基数排序法的效率高于其它的稳定性排序法。本文算法采用最低位优先法，简称LSD法：先从kd(最低位)开始排序，再对kd-1进行排序，依次重复，直到对k1(最高位)排序后便得到一个有序序列。
int Sort::MaxBit() {
int d = 1;//初始化记位数为1
int r = 10;//r代表基数
for (int i = 1; i < this->len; i++) {
while (this->array[i]>=r)
{
r *= 10;
d++;
}
}
return d;
}
void Sort::RadixSort() {
int d = MaxBit();//寻找待排序序列中最大数的位数
queue<int> *queue_list[10];//定义十个队列
queue<int> *queue_total = new queue<int>;//存放每趟排序的结果
for (int i = 0; i < 10; i++) {//给十个队列申请空间
queue<int> *q = new queue<int>;
queue_list[i] = q;
}
for (int i = 1; i < this->len; i++) {//将待排序序列存入队列
queue_total->push(this->array[i]);
}
for (int i = 0; i < d; i++) {
unsigned int size = queue_total->size();
for (unsigned int j = 0; j < size; j++) {
int temp = int(queue_total->front() /pow(10,i));
int value = temp % 10;//获取对应位的值
queue_list[value]->push(queue_total->front());//将数放入队列
queue_total->pop();//删除已出队的数
}
for (int m = 0; m < 10; m++) {
unsigned int queue_len = queue_list[m]->size();
for (unsigned int n = 0; n < queue_len; n++) {
if (!queue_list[m]->empty()) {
queue_total->push(queue_list[m]->front());
queue_list[m]->pop();
}
}
}
}
if (queue_total->size() == (this->len - 1)) {
for (int i = 1; i < this->len; i++) {
this->array[i] = queue_total->front();
queue_total->pop();
}
}
———————————————————————————————————————————————————————
类定义如下：
#pragma once
#include<iostream>
#include<cstdlib>
#include<queue>
#include<math.h>
using namespace std;
class Sort
{
public:
Sort();
Sort(int len, int *array);
~Sort();
void InsertSort();//直接插入排序
void HalfInsertSort();//折半插入排序
void ShellSort();//希尔排序
void BubbleSort();//冒泡排序
int Partition(int low,int high);//快速排序划分
void QuickSort(int low, int high);//快速排序
void SelectSort();//选择排序
void BuildMaxHeap();//建立最大堆
void AdjustDown(int k,int len);//调整结点
void HeapSort();//堆排序
void Merge(int low, int mid, int high);//归并
void MergeSort(int low, int high);//归并排序
int MaxBit();//获取数组中最大数的位数
void RadixSort();//distrution sort基数排序
int GetLen();
int *array;
private:
int len;
int *B;//归并排序辅助数组
};
转载：https://blog.csdn.net/qq_40945306/article/details/100655524
查看评论