排序算法总结

关于各种排序算法的总结表格,这里偷个懒直接用Simple life的博客http://blog.csdn.net/whuslei/article/details/6442755中的图片了

下面是自己写的各种排序的程序:

  1 #include<iostream>
  2 using namespace std;
  3 
  4 void swap(int *num,int i,int j)
  5 {
  6     int temp=num[i];
  7     num[i]=num[j];
  8     num[j]=temp;
  9 }
 10 //插入排序
 11 void sort_charu(int *num,int n)
 12 {
 13     for(int i=1;i<n;i++)
 14     {
 15         if(num[i]<num[i-1])
 16         {
 17             int temp=num[i];
 18             int j=i-1;
 19             while(j>=0 && temp<num[j])
 20             {
 21                 num[j+1]=num[j];
 22                 j--;
 23             }
 24             num[j+1]=temp;
 25         }
 26         
 27     }
 28 }
 29 ///////////////////////////////
 30 //shell排序
 31 void sort_shell(int *num,int n)
 32 {
 33     int d=n;
 34     while(d>1)
 35     {
 36         d=d/2;
 37         for(int i=d;i<n;i=i+1)
 38         {
 39             if(num[i]<num[i-d])
 40             {
 41                 int temp=num[i];
 42                 int j=i-d;
 43                 while(num[j]>temp&&j>=0)
 44                 {
 45                     num[j+d]=num[j];
 46                     j=j-d;
 47                 }
 48                 num[j+d]=temp;
 49             }
 50         }
 51     }
 52 }
 53 ////////////////////////////////////////////////
 54 //选择排序
 55 void sort_xuanze(int *num,int n)
 56 {
 57     int i,j;
 58     for(i=n-1;i>=0;i--)
 59     {
 60         int max=num[0];
 61         int xiabiao=0;
 62         for(j=1;j<=i;j++)
 63         {    
 64             if(max<num[j])
 65             {
 66                 max=num[j];
 67                 xiabiao=j;
 68             }
 69         }
 70         swap(num,i,xiabiao);
 71     }
 72 }
 73 /////////////////////////////////
 74 //堆排序
 75 //将num数组中s到n的数据建立成为大顶堆
 76 void heapadjust(int *num,int s,int n)
 77 {
 78     int temp=num[s];
 79     for(int i=2*s;i<=n;i=i*2)
 80     {
 81         if(i<n && num[i+1]>num[i])
 82         {
 83             i++;
 84         }
 85         if(temp<num[i])
 86         {
 87             num[s]=num[i];
 88             s=i;
 89         }
 90     }
 91     num[s]=temp;
 92 }
 93 
 94 void sort_dui(int *num,int n)
 95 {
 96     //从最后一个非叶子节点开始组建大顶堆
 97     for(int i=n/2;i>0;i--)
 98     {
 99         heapadjust(num,i,n);
100     }
101     //每次将第一个元素与堆顶元素交换,然后重新调整堆
102     for(int i=n;i>1;i--)
103     {
104         swap(num,i,1);
105         heapadjust(num,1,i-1);
106     }
107 }
108 //冒泡排序
109 void sort_maopao(int *num,int n)
110 {
111     int flag=1;
112     for(int i=n-1;i>0 && flag==1;i--)
113     {
114         flag=0;
115         for(int j=0;j<i;j++)
116         {
117             if(num[j]>num[j+1])
118             {
119                 swap(num,j,j+1);
120                 flag=1;
121             }
122         }
123 
124     }
125 }
126 ///////////////////////////////////
127 //快速排序
128 void sort_quick_diedai(int *num,int start,int end)
129 {
130     int temp=num[start];
131     int i=start;
132     int j=end;
133     if(start<end)
134     {
135         while(i<j)
136         {
137             while(num[j]>=temp&&j>i)
138             {
139                 j--;
140             }
141             if(i<j)
142             {
143                 num[i]=num[j];
144                 i++;
145             }
146             while(num[i]<=temp && i<j)
147             {
148                 i++;
149             }
150             if(i<j)
151             {
152                 num[j]=num[i];
153                 j--;
154             }
155         }
156         num[i]=temp;   
157         sort_quick_diedai(num,start,i);
158         sort_quick_diedai(num,i+1,end);
159     }
160 }
161 void sort_quick(int *num,int n)
162 {
163     sort_quick_diedai(num,0,n-1);
164 }
165 ///////////////////////////////////////////////////
166 //归并排序
167 //将num看成两个有序的数组,num[start...mid]和num[mid+1...end],将其合并为一个有序的数组
168 void merge_num(int *num,int start,int mid,int end,int *p)
169 {
170     int i=start;
171     int j=mid+1;
172     int k=0;
173     while(i<=mid &&j<=end)
174     {
175         if(num[i]<=num[j])
176         {
177             p[k++]=num[i++];
178         }
179         if(num[j]<=num[i])
180         {
181             p[k++]=num[j++];
182         }
183     }
184     while(i<=mid)
185     {
186         p[k++]=num[i++];
187     }
188     while(j<=end)
189     {
190         p[k++]=num[j++];
191     }
192     for(int i=0;i<k;i++)
193     {
194         num[start+i]=p[i];
195     }
196 
197 }
198 void sort_guibing_digui(int *num,int start,int end,int *p)
199 {
200     if(start<end)
201     {
202         int mid=(start+end)/2;
203         sort_guibing_digui(num,start,mid,p);
204         sort_guibing_digui(num,mid+1,end,p);
205         merge_num(num,start,mid,end,p);
206     }
207 }
208 void sort_guibing(int *num,int n)
209 {
210     int *p=new int[n];
211     sort_guibing_digui(num, 0, n-1,p);
212     delete []p;
213 }
214 
215 void print(int *num,int n)
216 {
217     for(int i=0;i<n;i++)
218     {
219         cout<<num[i]<<" ";
220     }
221     cout<<endl;
222 }
223 int main()
224 {
225     int num[10]={0,45,12,4,54,5,1,2,4,6};
226     //sort_charu(num,10);
227     //sort_xuanze(num,10);
228     //sort_maopao(num,10);
229     //sort_quick(num,10);
230     //sort_shell(num,10);
231     //sort_dui(num,9);//由于二叉树的性质所致,堆排序是从编号为1开始排序
232     sort_guibing(num,10);
233     print(num,10);
234     return 0;
235 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java企业面试——Java基础

1. Java基础部分 1.1 Java中的方法覆盖(Overwrite)和方法重载(Overloading)是什么意思? 重载Overload表示同一个类中...

2864
来自专栏Golang语言社区

深入分析golang多值返回以及闭包的实现

一、前言 golang有很多新颖的特性,不知道大家的使用的时候,有没想过,这些特性是如何实现的?当然你可能会说,不了解这些特性好像也不影响自己使用golang,...

5186
来自专栏从零开始学 Web 前端

01 - JavaSE之基础及面向对象

byte(-128 ~ 127) short(-32768 ~ 32767) int(-2147483648 ~ 2147483647)

1734
来自专栏Web行业观察

你所不知道的JSON

JSON已经逐渐替代XML被全世界的开发者广泛使用。本文深入讲解JavaScript中使用JSON.stringify的一些细节问题。首先简单回顾一下JSON和...

1212
来自专栏AI研习社

最常见的 35 个 Python 面试题及答案(2018 版)

作为一个 Python 新手,你必须熟悉基础知识。在本文中我们将讨论一些 Python 面试的基础问题和高级问题以及答案,以帮助你完成面试。包括 Python ...

8203
来自专栏专注数据中心高性能网络技术研发

[Effective Modern C++(11&14)]Chapter 3: Moving to Modern C++

2376
来自专栏大闲人柴毛毛

深入理解java异常处理机制

 1. 引子        try…catch…finally恐怕是大家再熟悉不过的语句了,而且感觉用起来也是很简单,逻辑上似乎也是很容易理解。不过,...

2454
来自专栏CaiRui

Python列表删除的三种方法

1、使用del语句删除元素 >>> i1 = ["a",'b','c','d'] >>> del i1[0] >>> print(i1) ['b', 'c',...

2688
来自专栏闻道于事

Java之异常处理

Java异常处理 异常:异常就是Java程序在运行过程中出现的错误。 异常由来:问题也是现实生活中一个具体事务,也可以通过java 的类的形式进行描述,并封装成...

3296
来自专栏古时的风筝

模板的简单介绍与使用

什么是模板? 模板(template)指c++中的函数模板与类模板,大体对应于C#和Java众的泛型的概念。目前,模板已经成为C++的泛型编程中不可缺少的一部分...

1898

扫码关注云+社区

领取腾讯云代金券