传统的排序方法多数是基于比较的,例如双向冒泡排序法
//双向冒泡排序
void sort1()
{
int a[7] = {1, 2, 3, 4, 5, 6, 7};
int i = 0,j = 0,zz = 0;
for (i = 0; i < 3; i++) {
for (j = 0; j < 6 - i; j++) {
if (a[j] < a[j + 1]) { zz = a[j]; a[j] = a[j + 1]; a[j + 1] = zz; }
if (a[6 - j] > a[5 - j]) { zz = a[6 - j]; a[6 - j] = a[5 - j]; a[5 - j] = zz; }
}
}
for (i = 0; i < 7; i++) {
cout << a[i] << endl;
}
}
虽然双向冒泡排序在原有冒泡排序基础上做了些改进,但时间复杂度依然是O(n2)
在学习了链表后有一种时间复杂度为O(nlog(r)m) )的排序算法,r为所采取的基数,而m为堆数。
基数排序简单来说就是从个位到高位一位一位的排序
下面在main函数里实现了一个简单的基数排序,对15个三位以内的数字进行排序。(链表类的定义请看上一篇博客)
#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
#include <math.h>
using namespace std;
int get_dc(int number, int figure);
int main()
{
int ar[15] = { 216,125,524,124,629,514,363,845,12,637,240,80,246,164,583 };
chain<int> *ori_list = new chain<int>(ar, 15);//创建链表读取原始数据
chain<int> *bin = new chain<int>[10];//使用链表建立十个箱子存放在某一位相同的数字
chain<int>* temp = new chain<int>(*ori_list);//复制一下原始数据到temp链表
int num,dc;//取出的元素,指定位数的数字
for (int j = 1; j <= 3; j++) {
while (!temp->empty()) {
num = temp->get(0);
dc = get_dc(num, j);
bin[dc].insert(bin[dc].size(), num);//插入必须在末尾
temp->erase(0);
}
for (int i = 0; i < 10; i++) {
while (!bin[i].empty()) {
temp->insert(temp->size(), bin[i].get(0));
bin[i].erase(0);
}
}
}
ori_list->output();
temp->output();
}
int get_dc(int number,int figure) //获取指定位数的数字
{
return number%int(pow(10,figure))/ pow(10,figure-1);
}
下面是用类的指针数组实现的,有一点改动
主要是定义指针数组这句chain<int> **bin = new chain<int>*[10];
#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
#include <math.h>
using namespace std;
int get_dc(int number, int figure);
int main()
{
int ar[15] = { 216,125,524,124,629,514,363,845,12,637,240,80,246,164,583 };
chain<int> *ori_list = new chain<int>(ar, 15);
chain<int> **bin = new chain<int>*[10];
for (int i = 0; i < 10; i++)
bin[i] = new chain<int>();
chain<int> *temp = new chain<int>(*ori_list);
int num,dc;//取出的元素,指定位数的数字
for (int j = 1; j <= 3; j++) {
while (!temp->empty()) {
num = temp->get(0);
dc = get_dc(num, j);
bin[dc]->insert(bin[dc]->size(), num);
temp->erase(0);
}
for (int i = 0; i < 10; i++) {
while (!bin[i]->empty()) {
temp->insert(temp->size(), bin[i]->get(0));
bin[i]->erase(0);
}
}
}
ori_list->output();
temp->output();
}
int get_dc(int number,int figure) //获取指定位数的数字
{
return number%int(pow(10,figure))/ pow(10,figure-1);
}
Comments 10 条评论
博主 匿名
手机也来戳一戳
博主 W
给最酷最酷的朋友来一次好认真的实名留言 solute!
博主 W
@W 回复一下我自己
然后敲回车换个行abaaba
博主 匿名
@W 回复的回复
博主 W
@W 评论一下我自己
然后h敲回车换个行abaabaaba
博主 卿非山谷
testing~
博主 匿名
666666
博主 xy
我虽然不懂但我大为震撼 -xy
博主 曹闻
程序编写习惯还有待加强!增加注释是很好的习惯!
博主 卿非山谷
@曹闻 收到!下次一定注意