Jiwu Bu
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  32 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
  1 #include <iostream>
  2 using namespace std;
  3 
  4 /*/////////////////////////////////////////////////////////////////////////
  5 以下为快速排序
  6 /////////////////////////////////////////////////////////////////////////*/
  7 /*
  8 冒泡排序
  9 算法：
 10 核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后
 11 交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好
 12 时间复杂度n*n  (n-1)*n/2
 13 */
 14 void BubbleSortData(int SortData[], int Length)
 15 {
 16     int tmpData =0;
 17     bool swapFlag =true;
 18 
 19     for (int i=Length-1; i>0 && swapFlag; i--)
 20     {
 21         swapFlag =false;
 22         for(int j=0; j<i; j++)
 23         {
 24             if ( SortData[j] > SortData[j+1])
 25             {
 26                 tmpData =SortData[j];
 27                 SortData[j] =SortData[j+1];
 28                 SortData[j+1] =tmpData;
 29                 swapFlag =true;
 30             }
 31         }
 32     }
 33 
 34     return;
 35 }
 36 /*
 37 快速排序是对起泡排序的一种改进，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键
 38 字小，则可分别对这两部分继续进行排序，以达到整个序列有序.
 39 交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大(小)于它
 40 时间复杂度为 n*logn,其平均性能最好，若初始记录序列按关键字有序或基本有序，快速排序将锐化为起泡排序
 41 */
 42 int  Partition(int SortData[], int low, int high)
 43 {
 44     int tmpData =SortData[low];//用于子表的第一个记录作枢轴记录
 45     int temp=0;
 46 
 47     while ( low<high )
 48     {
 49         //从表的两端交替的向中间扫描
 50         while (low<high && SortData[high]>=tmpData)
 51         {
 52             high--;
 53         }
 54         //将比枢轴记录小的记录移到低端
 55         SortData[low] =SortData[high];
 56 
 57         while (low<high && SortData[low]<=tmpData)
 58         {
 59             low++;
 60         }
 61         //将比枢轴记录大的记录移到高端
 62         SortData[high] =SortData[low];
 63     }
 64     //枢轴记录到位
 65     SortData[low] =tmpData;
 66 
 67     return low;//返回枢轴所在位置
 68 }
 69 
 70 void QuickSortData(int SortData[], int low, int high)
 71 {
 72     int offset;
 73 
 74     if ( low<high )
 75     {
 76         offset =Partition(SortData, low, high);
 77         QuickSortData(SortData, low, offset-1);
 78         QuickSortData(SortData, offset+1, high);
 79     }
 80 }
 81 
 82 /*/////////////////////////////////////////////////////////////////////////
 83 以下为插入排序
 84 /////////////////////////////////////////////////////////////////////////*/
 85 /*
 86 直接插入排序
 87 算法：经过i-1遍处理后，L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，
 88 使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。
 89 首先比较L[i]和L[i-1]，如果L[i-1]<=L[i]，则L[1..i]已排好序，第i遍处理就结束了;
 90 否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，
 91 使得L[j] ≤L[j+1]时为止
 92 优点:移动元素次数少，只需要一个辅助空间
 93 时间复杂度n*n
 94 当待排序记录的数量n很小时，这是一种很好的排序方法。但是n很大时，则不适合
 95 */
 96 void InsertSortData(int SortData[], int Length)
 97 {
 98     int tmpData =0;
 99     int i=0;
100     int j=0;
101 
102     for(i=1; i<Length; i++)
103     {
104         if ( SortData[i] <SortData[i-1])
105         {
106             tmpData =SortData[i];
107             //数据往后移动
108             for (j=i-1; j>=0 && tmpData<SortData[j]; j--)
109             {
110                 SortData[j+1] =SortData[j];
111             }
112             //将数据插入到j+1位置
113             SortData[j+1] =tmpData;
114         }
115     }
116 
117     return;
118 }
119 
120 /*
121 拆半插入排序所需要的辅助空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。
122 因为时间复杂度仍为n*n
123 */
124 void BInsertSortData(int SortData[], int Length)
125 {
126     int tmpData =0;
127     int i=0;
128     int j=0;
129     int low;
130     int high;
131     int middle;
132 
133     for(i=1; i<Length; i++)
134     {
135         tmpData =SortData[i];
136         low =0;
137         high =i-1;
138         //在r[low..high]中折半查找有序插入的位置
139         while ( low<=high )
140         {
141             middle =(low+high)/2;
142             if ( tmpData <SortData[middle] )
143             {
144                 high =middle-1;
145             }
146             else
147             {
148                 low =middle+1;
149             }
150         }
151         //记录后移
152         for (j=i-1; j>=high+1; j--)
153         {
154             SortData[j+1] =SortData[j];
155         }
156         SortData[high+1] =tmpData;
157     }
158 
159     return;
160 }
161 
162 
163 //////////////////////////////////////////////////////////////////////////
164 
165 /*
166 简单选择排序
167 算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。
168 所需移动的操作次数最少为0,,最大为3(n-1)
169 然而无论记录的初始排列如何，需要比较的次数相同n(n-1)/2 复杂度为n*n
170 */
171 void SelectSortData(int SortData[], int Length)
172 {
173     int tmpData;
174     int offset =0;
175     int j=0;
176 
177     for (int i=0; i<Length-1; i++)
178     {
179         offset =0;
180         tmpData =SortData[i];
181         for (j=i+1; j<Length; j++)
182         {
183             if ( tmpData>SortData[j] )
184             {
185                 tmpData =SortData[j];
186                 offset =j;
187             }
188         }
189 
190         if( offset >i)
191         {
192             SortData[offset] =SortData[i];
193             SortData[i] =tmpData;
194         }
195     }
196 
197     return;
198 }
199 
200 int main()
201 {
202     //int Buffer[] ={1,2,3,4,5,6};
203     int Buffer[] ={6,5,4,3,2,1};
204 
205     QuickSortData(Buffer,0, 5);
206 
207     for (int i=0; i<6; i++)
208     {
209         cout<<Buffer[i]<<" ";
210     }
211     cout<<endl;
212 
213     return 0;
214 }
215 http://www.cppblog.com/Files/bujiwu/SortData.rar

posted on 2008-10-25 23:53 bujiwu 阅读(6860) 评论(1)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序) 2008-10-26 14:40 金山词霸2008
太全了，而且算法介绍也很细致。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理