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

1.交换排序

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

1.1 冒泡排序

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

算法实现：

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

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

1.2.2算法实现二：

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

1.3. 总结

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