【超详细】一文弄懂快速排序算法（附快速排序、冒泡排序代码）

快速排序，是一种既不浪费空间，算法执行效率又快速的“折中”排序算法，适用于顺序很乱、很长的数字序列，

一、快速排序的算法原理

每次都取数组的第一个元素作为基准元素，凡是大于基准元素的都放在它的右边，凡是小于基准元素的都放在它的左边，具体步骤如下：

第一轮排序：

1、令第一个元素为基准元素，并设置两个变量i和j（也称为哨兵i、哨兵j）， i在序列的最左端，j在序列的最右端。（i = left；j = right）

2、j 从右往左试探，直到 j 找到小于基准元素值的元素就停止先； i 从左往右试探，直到 i 找到大于基准元素值的元素就停止。当 i 和 j 都停止了后，交换 i 和 j 所指向的元素。交换后， j 、 i 按以上步骤继续试探。

3、直到 i 和 j 相遇之后，则i的值与基准元素交换，第一轮排序结束。

第一轮排序结束后，分别对基准元素左右两边的序列重复以上步骤。

二、快速排序示例及其示意图

$6\qquad2\qquad7\qquad3\qquad9\qquad8$

快速排序算法示意图

三、快速排序代码、冒泡排序代码

QuickSort.c 快速排序

#include <stdio.h>
#include <malloc.h>

void QuickSort(int *Array, int left, int right);    //快速排序

int main(int argc, char const *argv[])
{
    int ARRAY_SIZE = 0;
    int *array;
    int i;

    //输入要排序数组的长度，并为指针变量 array 动态分配内存
    printf("请输入要排序的数组长度：");
    scanf("%d", &ARRAY_SIZE);
    
    array = (int *)malloc(ARRAY_SIZE*sizeof(int));

    //输入要排序数组的各个元素的值
    printf("请输入%d个数组元素（以空格隔开）：\n", ARRAY_SIZE);
    for(i = 0; i < ARRAY_SIZE; i++)
    {
        scanf("%d", &array[i]);
    }
    printf("\n");


    /**快速排序**/
    QuickSort(array, 0, ARRAY_SIZE-1);

    //输出排序后的数组元素值
    printf("排序后的数组为：");
    for(i = 0; i < ARRAY_SIZE; i++)
    {
        printf("%d ", array[i]);
    }
    printf("（从小到大）\n");

    return 0;
}

//快速排序
void QuickSort(int *Array, int left, int right)
{
    int pivot;
    int i, j;
    int swap_tmp;

    if(left > right)
        return ;

    pivot = Array[left];
    i = left;
    j = right;
    
    while(i != j)
    {
        while((Array[j] >= pivot) && (i < j))
            j--;
        while((Array[i] <= pivot) && (i < j))
            i++;
        
        if(i < j)
        {
            swap_tmp = Array[i];
            Array[i] = Array[j];
            Array[j] = swap_tmp;
        }
    }
    //pivot = Array[left];
    Array[left] = Array[i]; //原基准元素 与 Array[i]或Array[j] 交换值
    Array[i] = pivot;
    //第一轮快速排序已结束

    QuickSort(Array, left, i-1);    //左边序列排序
    QuickSort(Array, i+1, right);   //右边序列排序
}

快速排序

BubbleSort.c 冒泡排序

#include <stdio.h>
#include <malloc.h>


void BublleSort(int *Array, int ArraySize);         //冒泡排序

int main(int argc, char const *argv[])
{
    int ARRAY_SIZE = 0;
    int *array;
    int i;

    //输入要排序数组的长度，并为指针变量 array 动态分配内存
    printf("请输入要排序的数组长度：");
    scanf("%d", &ARRAY_SIZE);
    
    array = (int *)malloc(ARRAY_SIZE*sizeof(int));

    //输入要排序数组的各个元素的值
    printf("请输入%d个数组元素（以空格隔开）：\n", ARRAY_SIZE);
    for(i = 0; i < ARRAY_SIZE; i++)
    {
        scanf("%d", &array[i]);
    }
    printf("\n");


    /**冒泡排序**/
    BublleSort(array, ARRAY_SIZE);

    //输出排序后的数组元素值
    printf("排序后的数组为：");
    for(i = 0; i < ARRAY_SIZE; i++)
    {
        printf("%d ", array[i]);
    }
    printf("（从小到大）\n");

    return 0;
}

//冒泡排序
void BublleSort(int *Array, int ArraySize)
{
    int i, j;
    int tmp;

    for(i = 0; i < (ArraySize-1); i++)
    {
        for (j = i + 1; j < ArraySize; j++)
        {
            if(Array[i] > Array[j])
            {
                tmp      = Array[i];
                Array[i] = Array[j];
                Array[j] = tmp;
            }
        }
    }
}

冒泡排序

最后编辑于：2020.08.25 18:09:19