冒泡排序与快速排序【C语言】

冒泡排序

基本思想

对有n个记录的序列进行冒泡排序，首先将第一个数字与第二个数字进行比较，若为逆序，则将两个数字的顺序交换。然后比较第二个数字与第三个数字，若为逆序，则将两个数字的顺序交换…依此类推，经过第一轮排序后，最大的数字将“下沉”到最后，每趟的比较次数依次减少。经过n-1轮排序，将得到一个递增的序列。

空间复杂度：O(1)

时间复杂度：O(n^2)

稳定性：稳定

代码实现

n个记录总共要进行n-1趟排序，第i趟的比较次数为n-i次。可以使用双层循环，外层循环控制第几轮排序，内层控制每一轮比较的次数。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
void Input(); //输入数组
void Output(); //输出数组
void BubbleSort(); //冒泡排序

int arr[MAXSIZE];
int count = 0;

//冒泡排序
void BubbleSort(){
    int i ,j ,temp;
    for ( i = 0; i < count-1; i++)
    {
        for ( j = 0; j < count-i-1; j++)
        {
            if (arr[j] > arr[j+1])
            {
               temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
            }
        }
    }
}
//输入函数
void Input(){
    int x,i;
    char s;
    printf("please input less than 100 numbers, end with enter:\n");
    for (i = 0; s != '\n'; i++)
    {
        scanf("%d",&arr[i]);
        s = getchar();
        count++;
    }
}

//输出函数
void Output(){
    printf("sorted numbers:\n");
    for (int i = 0; i < count; i++){
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

int main(){
    Input();
    BubbleSort();
    Output();
    system("pause");
    return 0;
}

运行结果：

快速排序

基本思想

快速排序是从冒泡排序改进而得的一种“交换”排序方法。采用的是一种分治的策略。

1. 先从数列中取出一个数作为基准数(称为枢轴)。

2. 将比基准数大的数全放到它的右边，小于或等于基准数的全放到它的左边。

3. 再对左右两部分重复第(2)步，直到各区间只有一个数，达到整个序列有序。

空间复杂度：最好：O(n lb n)，最坏：O(n)

时间复杂度：平均：O(n lb n)，最坏：O(n^2)

稳定性：不稳定

代码实现

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
void Input(); //输入数组
void Output(); //输出数组
int Partition(int low ,int high);//一趟快速排序排
void QuikSort(int s, int e); //快速排序

int arr[MAXSIZE];
int count = 0;
//一趟快排
//定义一个high，low，key(记录枢轴的值)
//最后将枢轴移到正确位置，返回枢轴的位置
int Partition(int low ,int high){
    arr[0] = arr[low]; //arr[0]记录枢轴，待排序列从arr[1]开始
    while (low < high)
    {
       while(low < high&&arr[high] >= arr[0])
            --high;
        arr[low] = arr[high];
       while (low < high&&arr[low] <= arr[0])
            ++low;
        arr[high] = arr[low];
    }
    arr[low] = arr[0];
    return low;  //返回枢轴的位置
}
//快排(递归调用)
void QuikSort(int s,int e){
    if (s < e) //s与e是待排序区域的上下界
    {
        int keyPosition = Partition(s,e); //对待排序列进行一次划分，并返回枢轴位置
        QuikSort(s,keyPosition-1);        //对左侧子序列递归排序
        QuikSort(keyPosition+1,e);        //对右侧子序列递归排序
    }
    
}
//输入函数
void Input(){
    int x,i;
    char s;
    printf("please input less than 100 numbers, end with enter:\n");
    for (i = 1; s != '\n'; i++)
    {
        scanf("%d",&arr[i]);
        s = getchar();
        count++;
    }
}

//输出函数
void Output(){
    printf("sorted numbers:\n");
    for (int i = 1; i <= count; i++){
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

int main(){
    Input();
    QuikSort(1,count);
    Output();
    system("pause");
    return 0;
}

运行结果：