#include <iostream>
using namespace std;
//各种排序方法:
/**冒泡排序法**/
//它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,而堆排序、快速排序均不具有稳定性。
void Bubble_sort(int s[],int len){
int i,j,flag;
for (i=len-1; i>=1; i--) {
flag=1;
for (j=i-1; j>=0; j--) {
if (s[i]<s[j]) {
swap(s[i], s[j]);
flag=0;
}
}
if (1==flag) {//表示已经排序完成
break;
}
}
}
/**插入排序法**/
//插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。
void Insert_sort(int s[],int len){
int i,j;
int temp;
for(i=1;i<len;i++){
temp=s[i];
for (j=i; j>0&&temp<s[j-1]; j--) {
s[j]=s[j-1];
}
s[j]=temp;
}
}
/**折半插入排序法**/
//当第i个元素要进行排序的时候,它前面的1到i-1位置上的数据是局部有序的,对于有序的数据序列,采用折半查找法去判断在何处插入i位置上的数据,就大大减少了需要比较的次数。
void HalfInsert_sort(int s[], int len){
int temp, low, high, i, j, mid;
for (i=1; i<len; ++i)
{
temp = s[i];
low = 0;
high = i - 1;
while (high >= low)
{
mid = (low + high) / 2;
if (temp < s[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (j=i-1; j>=low; --j)
{
s[j+1] = s[j];
}
s[low] = temp;
}
}
/**希尔排序法**/
//希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。
void Hill_sort(int s[],int len){
int h,j,k,t;
for (h=len/2; h>0; h=h/2) {//控制增量
for (j=h;j<len; j++) {
t=s[j];
for (k=j-h; k>=0&&t<s[k]; k-=h) {
s[k+h]=s[k];
}
s[k+h]=t;
}
}
}
/**快速排序法**/
//快速排序(Quicksort)是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
//挖坑法
void quick_sort1(int s[],int l, int r){
int i=l;
int j=r;
int x=s[i];//第一个坑
if(i>=j) return ;
while (i!=j) {
//从右向左找小于x的数来填s[i];
while (i<j&&s[j]>=x) {
j--;
}
s[i]=s[j];
//从左向右找大于或等于x的数来填s[j];
while (i<j&&s[i]<x) {
i++;
}
s[j]=s[i];
}
s[i]=x;
quick_sort1(s, l, i-1);
quick_sort1(s, i+1, j);
}
/**简单选择排序法**/
//选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾(目前已被排序的序列)。以此类推,直到所有元素均排序完毕。
void Select_sort(int s[], int len){
int i,j,min;
for (i=0; i<len-1; i++) {
min=i;
for (j=i+1; j<len; j++) {
if (s[min]>s[j]) {
min=j;//把值最小的下标记下来
}
}
if (min!=i) {
swap(s[i], s[min]);
}
}
}
//输出
void prain(int s[],int len){
for (int i=0; i<len; i++) {
cout<<s[i]<<" ";
}
cout<<endl;
}
int main(int argc, const char * argv[])
{
//从小到大排序
int s[]={10,1,4,2,3,8,7,6,5,9};
int len=sizeof(s)/sizeof(int);
/**起泡排序法**/
Bubble_sort(s,len);
cout<<"冒泡法:";
prain(s, len);
cout<<endl;
/**插入排序法**/
int s1[]={10,1,4,2,3,8,7,6,5,9};
int len1=sizeof(s1)/sizeof(int);
Insert_sort(s1,len1);
cout<<"插入法:";
prain(s1, len1);
cout<<endl;
/**希尔排序法**/
int s2[]={10,1,4,2,3,8,7,6,5,9};
int len2=sizeof(s)/sizeof(int);
Hill_sort(s2,len2);
cout<<"希尔排序法:";
prain(s2, len2);
cout<<endl;
/**快速排序法**/
int s3[]={10,1,4,2,3,8,7,6,5,9};
int len3=sizeof(s)/sizeof(int);
Insert_sort(s3,len3);
/**简单选择排序法**/
int s4[]={10,1,4,2,3,8,7,6,5,9};
int len4=sizeof(s)/sizeof(int);
Select_sort(s4,len4);
cout<<"简单选择排序法:";
prain(s4, len4);
cout<<endl;
/**折半插入排序法**/
int s5[]={10,1,4,2,3,8,7,6,5,9};
int len5=sizeof(s)/sizeof(int);
HalfInsert_sort(s5,len5);
cout<<"折半插入法:";
prain(s5, len5);
cout<<endl;
return 0;
}
分享到:
相关推荐
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
直接插入、折半插入、冒泡、快速、简单选择等排序方法 用c语言实现 代码运行正常 不会有任何的问题
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
随机生成小于5000的数 根据操作通过不同的方法排序 泡泡排序 直接插入排序 折半插入排序 希尔排序 直接选择排序 统计时间 比较次数和交换次数 保存为txt文件
七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序) 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法,使得所有负数位于非负数之前,给出算法的性能...
C语言所有排序大全,解决了您日常上课考试学习的需要,在这里每一个程序都没有错误,其中压缩包包括了归并排序;基数排序;快速排序;冒泡排序;...希尔排序这些日常排序,因为是全集所以大家踊跃下载
常见的几种排序方式,包括选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序。vs2008实现,对话框方式,主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集,不能用...
希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
老师留的算法作业包含了 冒泡,选择,快速,归并,插入,折半插入,希尔,堆排序,包括了每个排序的比较次数和交换次数
快速排序 希尔排序 插入排序 折半排序算法
直接插入排序、希尔排序、冒泡排序、直接选择排序、堆排序、归并排序
提供五种排序算法的C++实现方法,输入(待排序元素个数、排序码上界(采用随机生成数组方式)),可选择输出(原始数组、排序后数组、原始数组有序度和无序度、排序过程中数据比较次数与数据移动次数、数组中出现...
直接插入排序、折半插入排序、希尔排列
冒泡,选择,插入,折半插入,希尔 排序 如冒泡: #include typedef struct number{ int k; }number; void bubblesort(number r[],int N) /*冒泡*/ { int falg,j,i,l; for(i=1;i;i++) { falg=1; for(j=1;j;j++)...
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
直接排序法,折半插入法,希尔排序法,快速排序法(c语言实现),适合初学数据结构的同学。全部程序都在VC++6.0调试通过。