常用的七大排序算法

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解压,如遇到无法解压的请联系管理员!

波比源码 » 常用的七大排序算法

发表评论

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

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