常用的七大排序算法

2015-03-05 为码而活 PHP教程 关注443次 已收录
当前位置：波比源码 > 常用的七大排序算法
正文概述

1：冒泡排序：

// BubbleSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*
冒泡排序是稳定排序
时间复杂度是 O(n^2)
*/

void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

void BubbleSort(int a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 1; j < n-i; j++)
{
if (a[j⑴] > a[j])
{
Swap(a[j⑴],a[j]);
}
}

}
}

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
BubbleSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

2：直接插入排序：

// InsertSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*
插入排序是稳定排序
插入排序：O(n^2);
*/

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}

void InsertSort(int a[], int n)
{
int i,j;

for ( i = 1; i < n; i++)//从1开始 a[0] 自动默许为有序
{
if (a[i] < a[i⑴])
{
int temp = a[i];
for (j = i⑴; j>=0 && a[j] > temp; j–)
{
a[j+1] = a[j];
}

a[j+1] = temp;//当遇到a[j] < temp的时候，a[j+1]赋值为temp
}

}

}

void InsertSort2(int a[], int n)
{
int i,j;
for(i = 1; i < n; i++)
{
if (a[i] < a[i⑴])
{
int temp = a[i];
for (j= i ⑴;j>=0 && a[j] > temp;j–)
{
a[j+1] = a[j];
}

a[j+1] = temp;

}
}
}

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
InsertSort2(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

3：希尔排序：

// ShellSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*
希尔排序：
1：希尔排序的本质是分组直接插入排序；

2：把记录按下标的1定增量分组，对每组使用直接插入排序算法排序；随着增量逐步减少，每组包括的关键词愈来愈多，
当增量减至1时，全部文件恰被分成1组，算法便终止。

3：希尔排序不是稳定的排序

4：希尔排序的时间复杂度： 比O(n^2)略微好1点

5：希尔排序是依照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，
速度很快；当元素基本有序了，步长很小，插入排序对有序的序列效力很高。所以，希尔排序的时间复杂度会比o(n^2)
好1些。

*/

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}

void ShellSort(int a[], int n)
{
int i;
int gap;

for(gap = n/2; gap>0; gap /= 2)
{
for ( i = gap; i < n; i++)
{
if (a[i] < a[i-gap])
{
int temp = a[i];
int j;
for ( j = i-gap; j>=0 && a[j] > temp; j -= gap)
{
a[j+gap] = a[j];
}
a[j+gap] = temp;
}
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
ShellSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

4：选择排序：

// SelectSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*

直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接插入排序
是将无序区的第1个元素直接插入到有序区以构成1个更大的有序区，而直接选择排序是从无序区
选1个最小的元素直接放到了有序区的最后

数组 a[0…n⑴]
1:初始时，数组全为无序区为 a[0…n⑴].令i=0;
2:在无序区a[i…n⑴]当选取1个最小的元素，将其与a[i]交换。交换以后a[0…i]就构成了1个有序区
3：i++并重复第2步知道 i == n⑴.排序完成

选择排序不是稳定排序
例如有： 5 8 5 2 9
第1次排序后 第1个 5与2 交换，那末两个5的相对位置产生了变化。

时间复杂度也是O(n^2)不过比冒泡排序整体来讲好1点

*/

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}

void Swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

void SelectSort(int a[], int n)
{
int i,j,nMin;
for (int i = 0; i < n; i++)
{
nMin = i;
for (int j = i+1; j < n; j++)
{
if (a[j] < a[nMin])
{
nMin = j;
}
}

Swap(a[nMin],a[i]);

}
}

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
SelectSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

5：归并排序：

// MergeSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*
归并排序：
时间复杂度： O(NlogN)
是稳定的排序

归并排序是建立在归并操作上的1种有效的排序算法,该算法是采取分治法（Divide and Conquer）的1个非常典型的利用。
将已有序的子序列合并，得到完全有序的序列；即先使每一个子序列有序，再使子序列段间有序。若将两个有序表合并成1个
有序表，称为2路归并。

归并进程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第1个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
否则将第2个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中1个有序表取完，然后再将
另外一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通经常使用递归实现，先把待排序区间[s,t]
以中点2分，接着把左侧子区间排序，再把右侧子区间排序，最后把左区间和右区间用1次归并操作合并成有序的区间[s,t]。

*/

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}

void mergeArray(int a[], int first, int mid, int last, int temp[])
{
int i = first;
int j = mid+1;
int m = mid;
int n = last;
int k = 0;

while (i <= m && j <= n)
{
if (a[i] <= a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}

while (i<=m)
{
temp[k++] = a[i++];
}
while (j<=n)
{
temp[k++] = a[j++];
}

for ( i = 0; i < k; i++)
{
a[first+i] = temp[i];
}
}

void mergeSort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first+last)/2;
mergeSort(a,first,mid,temp);//左侧排序
mergeSort(a,mid+1,last,temp);//右侧排序
mergeArray(a,first,mid,last,temp);//合并两个有序数列
}
}

bool MergeSort(int a[], int n)
{
int *p = new int[n];
mergeSort(a,0,n⑴,p);
delete[] p;

return true;
}

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);
cout<<"排序前："<<endl;
PrintNum(a,Num);
MergeSort(a,Num);
cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

6：快速排序：

// QuickSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*
快速排序的排序效力在同为O(NLogN)的几种排序方法中效力较高
快速排序的思路： 挖坑填数+分治法

1：先从数组当中取1个数作为基准数 例如 a[0]
2: 分区进程，将比这个数大的数全部放到它的右侧，小于或等于它的数全部放到它的左侧
3：再对左右区间重复第2步，直到各区间只要1个数

快速排序不是稳定的排序，这也是它与归并排序相比最大的缺点
eg： 3 2 4 5 6 2 7
第1步 从右往做找到比a[0]小的数字2，2填充到3 的位置，那末两个2 的相对位置产生了变化，所以不是稳定的排序
*/

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}
void QuickSort(int a[], int start, int end)
{
if (start > end)
{return;}

int i = start;
int j = end;
int k = a[i];//a[i]是第1个坑
while (i < j)
{
//从右往左找小于k的数来填 a[i]
while (i < j && a[j] >= k)
{
j–;
}
if (i < j)
{
a[i] = a[j];//将a[j]填到a[i]中，a[j]就是新的1个坑
}
//从左往右找大于k的数来填 a[j]
while (i < j && a[i] < k)
{
i++;
}
if (i < j)
{
a[j] = a[i];//将a[i]填到a[j]中，a[i]又是新的1个坑
}
}
//退出时，i=j，将k填到这个坑当中
a[i] = k;
QuickSort(a,i+1,end);
QuickSort(a,start,i⑴);

}

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);

cout<<"排序前："<<endl;
PrintNum(a,Num);

QuickSort(a,0,Num⑴);

cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

7：堆排序：

// HeapSort.cpp : 定义控制台利用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/*

不稳定：就是大小相同的两个数，经过排序后，终究位置与初始位置交换了。

快速排序：27 23 27 3以第1个27作为pivot中心点，则27与后面那个3交换，构成3 23 27 27，
排序经过1次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。

堆排序：比如：3 27 36 27，如果堆顶3先输出，则，第3层的27（最后1个27）跑到堆顶，
然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第2个位置的27输出，不稳定。

*/

void PrintNum(int a[],int n)
{
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
}

void HeapAdjust(int a[], int start, int end)
{
int temp = a[start];

for (int i = 2*start + 1; i <= end ; i*=2)
{
if (i<end && a[i]<a[i+1])//左右孩子比较
{
++i;//如果左孩子的值小于右孩子的值，则++i, i为较大的记录的下标
}
else
{
//i不做处理
}

if (temp > a[i]) //左右孩子中获胜者与父亲的比较
{
break;//如果左右孩子中最大的都比父节点的值小，则不需要做处理
}
else
{
//将孩子节点进行上位，则以孩子节点的位置进行下1轮的挑选
a[start] = a[i];
start = i;
}
}
a[start] = temp;
}

void HeapSort(int a[], int n)
{
//先建立大顶堆
for (int i = n/2; i >=0; –i)
{
HeapAdjust(a,i,n);
}

//进行排序
for (int i = n⑴; i > 0 ; –i)
{
//最后1个元素和第1元素进行交换
int temp = a[i];
a[i] = a[0];
a[0] = temp;

//然后将剩下的无序元素继续调剂为大顶堆
HeapAdjust(a,0,i⑴);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55};
int Num = sizeof(a)/sizeof(a[0]);

cout<<"排序前："<<endl;
PrintNum(a,Num);

HeapSort(a,Num);

cout<<endl<<"排序后："<<endl;
PrintNum(a,Num);

getchar();
return 0;
}

 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » 常用的七大排序算法
分享到：

相关推荐

46 评论

  3. order ampicillin 250mg generic generic acillin brand erythromycin 500mg

  11. clozaril 50mg without prescription decadron tablet buy decadron 0,5 mg generic

  15. order orlistat online cheap diltiazem uk acyclovir 400mg generic

  16. purchase cialis without prescription cheap plavix 150mg plavix 75mg generic

  17. order sildenafil for sale sildenafil order order cialis 10mg for sale

  20. online casino usa best casinos casinos online

  27. buy tadacip 10mg without prescription plavix 75mg tablet amoxicillin 500mg price

  30. oral cialis Cialis visa buy ed pills best price

  31. modafinil 100mg cost stromectol humans promethazine 25mg over the counter

  35. purchase isotretinoin without prescription isotretinoin 20mg uk buy azithromycin 250mg sale

  39. buy ditropan 2.5mg online purchase oxybutynin order trileptal 300mg online cheap

发表评论

Hi, 如果你对这款模板有疑问，可以跟我联系哦！

联系站长
赞助VIP 享更多特权，建议使用 QQ 登录
QQ登录
喜欢我嘛？喜欢就按“ctrl+D”收藏我吧！♡