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

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

1.交换排序

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

1.1 冒泡排序

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

算法实现：

#include // 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;}

1.2.快速排序

算法思想： 从无序区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]。这个过程为一次划分交换排序。然后再对左右两个无序区各自进行划分排序，直到无序区都排好序为止。因为每一次划分交换排序的过程一样，只是待排序区间的不同，因此可以采用递归算法来完成。

1.2.1.算法实现一：

#include 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;}

1.2.2算法实现二：

#include // 对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;}

1.3. 总结

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。