快速排序（C语言）_快速排序c语言代码

目录

一、简介

二、代码部分

2.1运行结果

三、代码部分分析

3.1核心代码

3.1.1介绍代码运行过程 

四、总结 

---

一、简介

中文名：快速排序

英文名：quick sort

时间复杂度：O(nlog2n)

稳定性：不稳定性的排序算法（多个相同的值的相对位置在也许会在算法结束后位置发生改变）

原理：将数组的第一个（最后一个）数组元素a，作为关键数据，将比a小的数字b放到a的左边（右边），所有比a小的数字b放到a的右边（左边），快速排序是对冒泡排序的的优化。

二、代码部分

int main()
{
    int arr[10] = {9,5,3,8,1,2,6,7,4,10};
    void quicksort(int a[10],int i,int j);  //函数的声明
 
    printf("排列前:");
    for(int i = 0; i < 10;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
 
    quicksort(arr,0,9);  //调用函数
 
    printf("排列后：");
    for(int i = 0; i < 10;i++)
    {
        printf("%d ",arr[i]);
    }
    system("pause");
    return 0;
}
 
void quicksort(int a[10],int first,int end)
{
    if(first > end)  //递归结束条件
    {
        return;
    }
    int i = first,j = end,flag = a[i],exchange = 0;
 
    while(i != j)
    {
        while(i < j && a[j] > flag)
        {
            j--;
        }
 
        while(i < j && a[i] <= flag)
        {
            i++;
        }
        if(j > i)
        {
            exchange = a[i];
            a[i] = a[j];
            a[j] = exchange;
        }
    }
    a[first] = a[i];
    a[i] = flag;
    quicksort(a,first,i - 1);
    quicksort(a,i + 1,end);
}

2.1运行结果

三、代码部分分析

3.1核心代码

void quicksort(int a[10],int first,int end)
{
    if(first > end)  //递归结束条件
    {
        return;
    }
    int i = first,j = end,flag = a[i],exchange = 0;
 
    while(i != j)
    {
        while(i < j && a[j] > flag)
        {
            j--;
        }
 
        while(i < j && a[i] <= flag)
        {
            i++;
        }
        if(j > i)
        {
            exchange = a[i];
            a[i] = a[j];
            a[j] = exchange;
        }
    }
    a[first] = a[i];
    a[i] = flag;
    quicksort(a,first,i - 1);
    quicksort(a,i + 1,end);
}

3.1.1介绍代码运行过程 

     原数组元素：如图： 

        首先我们先将数组的第一个元素 9 赋值给 flag ,(flag 起标记作用)。

        j 从数组元素的最后一个下标 9出发 ，每次循环 j-- ，直到找到比 flag 小的数字，再记录这个数字的下标。

        i 从数组元素的开头下标 0 出发，每次循环 i++,直到找到比 flag 大的数字，再记录这个数字的下标。

         当 i  和 j 都找到了自己相对应的数字，且  i != j 二者就交换数值。

         当 i == j 时，就和 flag 交换数值。（这也意味着第一次排序的结束）

          ① j-- 寻找比 flag 小的数字，当 j == 8,时找到 a[8] == 4 小于 9，成立；紧接着 i++ 寻找比 flag 大的数字，当 i == 8，时还是没有找到比 flag 大的数字，这时 i  == j，所以就将 a[8] 和 flag 进行交换。如下图：

           交换后（如下图）： 

          接下来数组被分成了两个部分：quicksort(a,0,7)  和 quicksort(a,9,9)。

其中 quicksort(a,9,9) 的 first == end，递归结束。（即数组中元素 9 和 10 排列完成）

所以接下来，我们把焦点放到 quicksort(a,0,7) 上（如下图）： 

  

           由上图可知：flag 继续记录着 a[0] 的值，j-- 寻找比 flag 小的数组元素，当 j == 5，时发现 a[5] == 2 小于 flag，然后我们的 i++ 出发寻找比 flag 大的数组元素，当 i == 1，时发现a[3] == 5 大于 flag，接下来到交换环节（a[1] 与 a[5] 交换），结果（如下图）： 

   

          接下来 j-- 继续前进，当 j == 4，时找到了a[4] == 1 小于 flag ，i++ 出发，当 i == 3，时找到比 flag 大的数组元素 8，交换结果（如下图）：

 

           紧接着，j-- 继续，当 j == 3，时 i == j，所以 a[3] 与 flag 交换数值（结果如下图）：

          接下来数组被分成了两个部分：quicksort(a,0,3)  和 quicksort(a,5,7)。运行过程与前面介绍的大径相同。最终我们可以得到如下结果：

四、总结 

          快速排序优点：排列速度快，比较简单；缺点：不稳定（如果数组是递增的有序数组，对它用快速排序需要N^2/2次操作）。

最后到这里，文章就结束了，如果在内容上有问题，恳请各位大佬们指出。