<12> 各 种 排 序

2018-01-11 12:46:39来源:网络收集作者:程序诗人人点击

分享

阿里云爆款

排序其实是我们在日常的项目开发中,比较常见的操作。比如:按”时间“将”帖子“排序,按”点击量“将”帖子“排序,按”观看数“将”视频“排序,按”分数“将学生的信息进行排序。这些都大量直接使用了排序的算法,或者间接的排序算法,或者是STL自带的算法,或者按照某个标准改良的排序算法等等。因此,了解常见排序算法的执行原理和执行过程,是理解排序的必要的条件。我们可以一起来看看常见的几种排序算法:


1 . 冒泡排序


2 . 插入排序


3 . 选择排序


4 . 希尔排序


5 . 归并排序


6 . STL排序


7 . 快速排序


8 . 堆排序


#include <iostream>
#include
#include
#include
#include
#include
#include
typedef __int64_Maxint;
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
// 各种排序 ( 升 序 )
// 冒 泡 排 序
void bubble(_Maxint* P, _Maxint size) {
int Temp = 0;
for (_Maxint i = 0; i < size; i++){
for (_Maxint ii = 0; ii < size-i-1; ii++){
if (P[ii] > P[ii + 1]) {
Temp = P[ii];
P[ii] = P[ii + 1];
P[ii + 1] = Temp;
}
}
}
}
// 插 入 排 序
void insert(_Maxint* P, _Maxint size) {_Maxint Temp;
_Maxint index;
for (_Maxint i = 1; i < size; i++){
Temp = P[i];
index = i;
while (index>0 && P[index-1]>Temp){
P[index] = P[index - 1];
index--;
}
P[index] = Temp;
}
}
// 选 择 排 序
void select(_Maxint* P, _Maxint size) {_Maxint Temp = 0;
_Maxint index = 0;
for (_Maxint i = 0; i < size; i++){
Temp = P[i];
for (size_t ii = i + 1; ii < size; ii++) {
if (P[ii] < Temp) {
Temp = P[ii];
index = ii;
}
}
P[index] = P[i];
P[i] = Temp;
}
}
// 希 尔 排 序
void shell(_Maxint* P, _Maxint size) {
// 增量为2
_Maxint step = size / 2;
_Maxint Temp = 0;
_Maxint index = 0;
while (step >= 1) {
for (size_t i = step + step; i < size; i += step) {
Temp = P[i];
index = i;
while (index>0 && P[index-step]>Temp){
P[index] = P[index - step];
index -= step;
}
P[index] = Temp;
}
step /= 2;
}
}
// 归 并 排 序
void mergearray(_Maxint* P, _Maxint left, _Maxint middle, _Maxint right, _Maxint* Temp) {
_Maxint i1 = left;
_Maxint i2 = middle + 1;
_Maxint i3 = 0;
while (i1 <= middle && i2 <= right) {
if (P[i1++] > P[i2++]) {
Temp[i3++] = P[i2++];
}
else {
Temp[i3++] = P[i1++];
}
}
while (i1 <= middle) {
Temp[i3++] = P[i1++];
}
while (i2 <= right) {
Temp[i3++] = P[i2++];
}
i3 = 0;
while (left <= right) {
P[left++] = Temp[i3++];
}
}
void mergesort(_Maxint* P, _Maxint left, _Maxint right, _Maxint* Temp) {
if (left < right) {
_Maxint middle = (left + right) / 2;
mergesort(P, left, middle, Temp);
mergesort(P, middle + 1, right, Temp);
mergearray(P, left, middle, right, Temp);
}
}
void merge(_Maxint* P, _Maxint size) {
_Maxint* Temp = new _Maxint[size];
mergesort(P, 0, size - 1, Temp);
}
// STL 排 序
void STLSort(_Maxint* P, _Maxint size) {
std::sort(P, P + size);
}
// 输 出
void Print(_Maxint* P,_Maxint size) {
for (size_t i = 0; i < size; i++){
std::cout << P[i] << " ";
}
std::cout << "/n" << std::endl;
}
int main() {
const _Maxint ArraySize = 30000;
srand((unsigned)time(NULL));
_Maxint *M = new _Maxint[ArraySize];
std::cout << "Origin:/t";
for (_Maxint i = 0; i < ArraySize; i++){
M[i] = rand() % 10000;
//std::cout << M[i] << " ";
}
std::cout << "Current Data' size is: " << ArraySize << "/n" << std::endl;//------------------------------------------------------------------------------------------------
_Maxint *M1 = new _Maxint[ArraySize];
std::memcpy(M1, M, ArraySize * sizeof(_Maxint));
double bubblestart = clock();
bubble(M1, ArraySize);
double bubblend = clock();
std::cout << "bubble:/t" << double(bubblend - bubblestart) / CLOCKS_PER_SEC << "s/n" << std::endl;//------------------------------------------------------------------------------------------------
_Maxint *M2 = new _Maxint[ArraySize];
std::memcpy(M2, M, ArraySize * sizeof(_Maxint));
double insertstart = clock();
insert(M2, ArraySize);
double insertend = clock();
std::cout << "insert:/t" << double(insertend - insertstart) / CLOCKS_PER_SEC << "s/n" << std::endl;
//------------------------------------------------------------------------------------------------
_Maxint *M3 = new _Maxint[ArraySize];
std::memcpy(M3, M, ArraySize * sizeof(_Maxint));
double selectstart = clock();
select(M3, ArraySize);
double selectend = clock();
std::cout << "select:/t" << double(selectend - selectstart)/ CLOCKS_PER_SEC << "s/n" << std::endl;//------------------------------------------------------------------------------------------------
_Maxint *M4 = new _Maxint[ArraySize];
std::memcpy(M4, M, ArraySize * sizeof(_Maxint));
double shellstart = clock();
shell(M4, ArraySize);
double shellend = clock();
std::cout << "Shel1:/t" << double(shellend - shellstart) / CLOCKS_PER_SEC << "s/n" << std::endl;
//------------------------------------------------------------------------------------------------
_Maxint *M5 = new _Maxint[ArraySize];
std::memcpy(M5, M, ArraySize * sizeof(_Maxint));
double mergetart = clock();
merge(M5, ArraySize);
double mergeend = clock();
std::cout << "merge:/t" << double(mergeend - mergetart) / CLOCKS_PER_SEC << "s/n" << std::endl;
//------------------------------------------------------------------------------------------------
_Maxint *M6 = new _Maxint[ArraySize];
std::memcpy(M6, M, ArraySize * sizeof(_Maxint));
double selstart = clock();
STLSort(M6, ArraySize);
double stlend = clock();
std::cout << "sel:/t" << double(stlend - selstart) / CLOCKS_PER_SEC << "s/n" << std::endl;
//------------------------------------------------------------------------------------------------
std::cout << "/n" << std::endl;
std::cin.get();
}测试用例为”数组大小为30000的整型数组“,运行后的结果是:

<12> 各 种 排 序
未完,待续。(需要对每一个排序方式进行详解)


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台