排序算法

1 #include 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

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

49 //从表的两端交替的向中间扫描

50 while (low=tmpData) 51 {

52 high--; 53 }

54 //将比枢轴记录小的记录移到低端 55 SortData[low] =SortData[high]; 56

57 while (low

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

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

104 if ( SortData[i]

106 tmpData =SortData[i]; 107 //数据往后移动

108 for (j=i-1; j>=0 && tmpData

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

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

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

179 offset =0;

180 tmpData =SortData[i]; 181 for (j=i+1; j

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<

211 cout<

212

213 return 0; 214 }

本文来源：https://www.bwwdw.com/article/cnwf.html