当前位置 : 主页 > 编程语言 > java >

数据结构排序系列之交换排序(二)

来源:互联网 收集:自由互联 发布时间:2022-08-10
1.交换排序 交换排序我们介绍冒泡排序和快速排序(划分交换排序),核心思想就是通过元素两两比较,发现反序时进行交换,直到所有元素都没有反序为止。 1.1 冒泡排序 算法思想:


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. 总结

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


上一篇:startActivityForResult 在Flutter中等价于什么
下一篇:没有了
网友评论