重温常见排序法

最新推荐文章于 2023-04-06 22:20:42 发布

laxian2009

最新推荐文章于 2023-04-06 22:20:42 发布

阅读量471

点赞数

分类专栏： C/C++ 文章标签：算法排序

本文链接：https://blog.csdn.net/laxian2009/article/details/49206097

版权

C/C++ 专栏收录该内容

6 篇文章

订阅专栏

1、冒泡排序法

算法简单，以长度为 len-1 的arr 数组为例：

1、从 0到 len-1 依次比较相邻位置的数，后者大于前者，交换位置

一轮过后，最后一个位置确定，是最大数。

2、第i轮只需比较 0 到 len-1-i 即可。

直到最后一轮结束，数组排序就完成了。

/* 冒泡排序 */

void bubble_sort(int *arr,int len) {

for (int i = 0; i < len; i++){
for (int j = 0; j < len-1-i; j++){
if (arr[j]>arr[j+1]){
arr[j] = arr[j] + arr[j + 1];
arr[j+1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
printArr(arr, len);
}
}

}}

2、选择排序法

和冒泡法步骤差不多。以长度为 len的arr数组为例：

第一轮：将 arr[1]-arr[len-1] 依次和 arr[0] 比较，小于arr[0]则交换。

第 i 轮：将 arr[i+1]-arr[len-1]一次和arr[0] 比较，小于arr[i]则交换

/* 选择排序 */

void select_sort(int *arr, int len) {

for (int i = 0; i < len - 1; i++) {
for (int j = i+1; j < len; j++) {
if (arr[i] > arr[j]) {
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
print(arr, len);
}
}

}}

3、插入排序法

又分为直接插入排序法和二分插入排序法

直接插入排序

/* 直接插入排序 */

void insert_sort(int *arr, int len) {

for (int i = 1; i < len; i++){//以第一个数作为有序数组，其余为无序数组

for (int j = i; j > 0 && arr[j-1]>arr[j]; j--){
arr[j] = arr[j] + arr[j - 1]; //交换arr[j]和arr[j-1];
arr[j-1] = arr[j] - arr[j - 1];
arr[j] = arr[j] - arr[j - 1];
}

}}

插入排序百度上讲的太抽象

第2个数和第1个比，小于第1个数，则交换之

第3个数和第2个比，小于则交换，第2个在和第1个比

...

第N个数和第N-1个比，小于则交行，...第2个和第1个

二分插入排序

 
   /* 二分插入排序 */ 
  
 
   void binary_insert_sort 
   ( 
   int 
   * arr 
   ,  
   int len 
   )  
   { 
  
for(int i  
  =1; i  
  < len 
  ; i 
  ++){//以第一个数为已排序数组
int l  
  =0, h  
  = i  
  -1;//有序数组0~i-1
int p  
  =(l  
  + h 
  )/2;//中间数位置
while(l  
  <= h 
  ){//二分查找
if(arr 
  [p 
  ]> arr 
  [i 
  ]) h  
  = p  
  -1;//左边
else l  
  = p  
  +1;//有吧
             p  
  =(l  
  + h 
  )/2;//重设中间点
}
for(int j  
  = i 
  ; j  
  > l 
  ; j 
  --){//插入点在l前
             arr 
  [j 
  ]= arr 
  [j 
  ]+ arr 
  [j  
  -1];
             arr 
  [j 
  -1]= arr 
  [j 
  ]- arr 
  [j  
  -1];
             arr 
  [j 
  ]= arr 
  [j 
  ]- arr 
  [j  
  -1];
}
        
   } 
   } 
  

4、希尔排序

希尔排序是直接插入排序的一种改进。

1、选择一个小于数组长度的增量 d ₁，我们选得 d ₁=len/2，对于0，0+ d ₁，0+2d ₁，...构成有一个数组

2、我们将其视为一个数组进行直接插入排序

3、然后再设置 d ₂， d ₂< d ₁，这里选择的 d ₂= d ₁/2重复第2步

4、直到d _n-1= 1， d _n< d _n-1，这时，分组变成一个

5、排序完成

/* 希尔排序 */

void shell_sort(int *arr,int len) {

int d = len / 2; //起始增量,为1，就是直接插入排序

while (d>=1){
for (int i = 0; i < d; i++) {
cout << "-----------------------" << endl;
int j = i + d;
while (j < len) {
for (int k = j; k > 0 && arr[k - d]>arr[k]; k -= d) {
arr[k] = arr[k] + arr[k - d]; //交换arr[j]和arr[j-1];
arr[k - d] = arr[k] - arr[k - d];
arr[k] = arr[k] - arr[k - d];
printArr(arr, len);
}
j += d;
}
}
d=(d == 1) ? 0 : d / 2;

}}

5、快速排序法

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数

快速排序又被称为分治法，确切的说是：挖坑填数+分治法

/* 快速排序 */

void quick_sort ( int *arr , int _l , int _h ) {
if (_l >= _h) return; //判断结束

int l = _l , h = _h ; //保存范围

int pivot = arr [_l ] ; //设置基准
while (l <h ) {
while ( (l < h ) & & arr [h ] > pivot ) h - - ; //右向左,找首个小于pivot的数,h指向它
arr [l ] = arr [h ] ;
while ( (l < h ) & & arr [l ] < pivot ) l + + ; //左向右,找首个大于pivot的数,l指向它
arr [h ] = arr [l ] ;
}
arr [l ] = pivot ; //重设基准
quick_sort (arr , _l , l - 1 ) ; //分区递归

quick_sort (arr , l + 1 , _h ) ;

}

6、归并排序

归并排序的思想是将两个有序数组合并成一个数组，合并后仍然有序

这就分成了两部分，一部分是有序数组的合并，一部分是分组递归

/*归并排序*/

void merge_array ( int *a , int f , int t , int m , int *r ) {

int i , j , k ;
i = f ;
k = 0 ;

j = m + 1 ;

//a数组中，f~m是一个数组，m+1~t是一个数组，将其合并到r中

while (i < = m & &j < = t ) {
if (a [i ] < a [j ] )
r [k + + ] = a [i + + ] ;
else
r [k + + ] = a [j + + ] ;
}
while (i < = m )
r [k + + ] = a [i + + ] ;
while (j < = t )
r [k + + ] = a [j + + ] ;
for ( int i = 0 ; i < = t - f ; i + + ) {
a [f + i ] = r [i ] ;
cout < < " a[ " < < f + i < < " ]= " < < a [f + i ] < < endl ;

}

}

void merge_sort ( int *arr , int l , int h , int m , int *r ) {
if (l <h ) {
merge_sort (arr , l , m , (l + m ) / 2 , r ) ;
merge_sort (arr , m + 1 , h , (m + 1 + h ) / 2 , r ) ;
merge_array (arr ,l ,h , (l +h ) / 2 ,r ) ;

}