数据结构排序系列之交换排序（二）

WTech 2020-05-08

312

交换排序

交换排序我们介绍冒泡排序和快速排序（划分交换排序），核心思想就是通过元素两两比较，发现反序时进行交换，直到所有元素都没有反序为止。

冒

泡

排

序

算法思想：

通过相邻元素之间的比较和交换来完成。冒泡排序从后往前，进行相邻元素的两两比较和交换。使关键字小的元素逐渐从底部移向顶部。

算法实现：

#include <stdio.h>








// R为待排序的数组,n是数组的长度
void bubbleSort(int R[],int n){
  // 进行n-1趟的比较与交换操作
  for(int i = 0; i < n-1; i++){




    int j = n - 1;
    while(j > i){ // 进行第i趟排序，while循环也可以换成for循环
      // 对比，交换
      if(R[j] < R[j-1]){
        int temp = R[j];
        R[j] = R[j-1];
        R[j-1] = temp;
      }
      j--;
    }
  }
}




int main(){
  int data[]={36,28,45,13,67,36,18,56};
  bubbleSort(data,8);
  for(int i = 0;i< 8; i++){
    printf("%d ",data[i]);
  }
  return 0;
}

快

速

排

序

算法思想：

从无序区R[low...high]中选择一个元素，假设为x，作为排序比较基准。用此基准将无序区分为R[low...i-1]和R[i+1...high]两个无序区，并使左边的无序区的元素的关键字都小于等于x，使右边的无序区的元素的关键字都大于等于x。而基准x则位于最终排序的位置i上，即R[low...i-1]≤R[i]≤R[i+1...high]。这个过程为一次划分交换排序。然后再对左右两个无序区各自进行划分排序，直到无序区都排好序为止。因为每一次划分交换排序的过程一样，只是待排序区间的不同，因此可以采用递归算法来完成。

算法实现一

#include <stdio.h>




void quickSort(int R[],int n,int i,int j){
  int low = i;
  int high = j;
  if(low == high && low >= 0 && high < n) return;
  int x = R[low];
  while(low != high){
    if(R[high] <= x){
      R[low] = R[high];
      low++;
      while(low != high){
        if(R[low] >= x){
          R[high] = R[low];
          break;
        }
        low++;
      }  
    }
    if(low != high){
      high--;
    }
  }
  R[low] = x; // R[high] = x也可以，此时low与high相等
  
  // 递归调用，完成其他划分排序交换
  if(low -1 >= i){
    quickSort(R,n,i,low-1);
  }
  if(low+1 <= j){
    quickSort(R,n,low+1,j);
  }
}




int main(){
  int data[] = {45,53,18,49,36,76,13,97,36,32};
  quickSort(data,10,0,9);
  for(int i =0; i < 10;i++){
    printf("%d ",data[i]);
  }
  return 0;
}

算法实现二

#include <stdio.h>




// 对R[low..high]进行一次划分交换排序
int partition(int R[],int n,int low,int high){
  if(n <= 0 || low < 0 || high < 0 || low >= high || high > n-1) return -1;
  int x = R[low];
  // 当low等于high时结束，low或high即为x的在排序中的位置
  while(low < high){
    // 向左移动
    while(low < high && R[high] > x){
      high--;
    }
    if(low < high){
        R[low] = R[high];
      low++;
    }
    // 向右移动
    while(low < high && R[low] < x){
      low++;
    }
    if(low < high){
      R[high] = R[low];
      high--;
    }
  }
  R[low] = x; // R[high] = x也可以
  return low;
}




// 通过递归的方式来完成排序
void quickSort(int R[],int n,int low,int high){
  if(n <= 0 || low < 0 || high < 0 || low >= high || high > n-1) return;
  int p = partition(R,n,low,high);
  printf("%d \n",p);
  for(int i = 0;i < n;i++){
    printf("%d ",R[i]);
  }
  printf("\n");
  if(p != -1){
    quickSort(R,n,low,p-1);
    quickSort(R,n,p+1,high);
  }
}
int main(){
  int data[] = {45,53,18,49,36,76,13,97,36,32};
  quickSort(data,10,0,9);
  for(int i =0; i < 10;i++){
    printf("%d ",data[i]);
  }
  return 0;
}

总结

冒泡排序是稳定的，快速排序（划分交换排序）是不稳定的。冒泡算法每次只比较和交换相信的元素，因而总的比较次数和移动次数较多，而快速排序的比较和交换是从两端向中间进行的，每次移动的距离都比较远，因而总的比较次数和总的移动次数较少。事实上，快速排序有非常好的时间复杂度，它优于其他各种排序算法。

end

数据库

文章转载自WTech，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构排序系列之交换排序（二）

评论