快速排序算法

万次阅读 多人点赞 2019-01-11 21:09:08

但是这种算法时间复杂度高，当需要排序的元素较多时，程序运行时间很长，因此产生了快速排序算法。该算法的实现可分为以下几步： 1. 在数组中选一个基准数（通常为数组第一个）； 2. 将数组中小于基准数的数据移到...

最开始学习编程，遇到排序问题，一般都是用冒泡法，因为冒泡法好理解，代码量少。但是这种算法时间复杂度高，当需要排序的元素较多时，程序运行时间很长，因此产生了快速排序算法。该算法的实现可分为以下几步：

1. 在数组中选一个基准数（通常为数组第一个）；

2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；

3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

例如有一需要排序的数组为：23,45,17,11,13,89,72,26,3,17,11,13（从小到大排序）：

选取数组第一个数23为基准数，存入temp变量中，从数组的左右两边界向中间进行遍历，定义两个指针 i 和 j，i 最开始指向数组的第一个元素，j 最开始指向数组的最后一个元素。指针 i 从左向右移动，指针 j 从右向左移动。先移动 j 指针（从右忘左移），当 j 指向的数大于基准数时，略过，j 继续往左移动，直到遇到小于等于基准数的数arr[j]，将arr[j]填入arr[i]中；再移动 i 指针，当 i 指向的数小于等于基准数时，略过，i 继续往右移动，直到遇到不比基准数小的数arr[i]，将arr[i]填入arr[j]中；再移动 i 指针，再移动 j 指针...(轮换移动)，直到 i 和 j 指针相遇，此时将temp（基准数）填入arr[i]中即完成算法的第2个步骤。接下来分别将基准数左边和右边的数组按照以上方法进行聚合，直到每个子集只有一个元素，即排序完成。

可能描述得有些抽象，接下来用图一步一步的示意：

将数组第一个数23赋给temp变量，指针 i 指向数组第一个元素，指针 j 指向数组最后一个元素



从 j 开始遍历（从右往左），遇到13时，因为13<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为13；



再从 i 遍历（从左往右），遇到45时，因为45>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为45；



继续从 j 遍历，遇到11时，因为11<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为11；



从 i 遍历，遇到89时，因为89>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为89；



从 j 遍历，遇到17时，因为17<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为17；



从 i 遍历，遇到72时，因为72>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为72；



从 j 遍历，遇到3时，因为3<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为3；



从 i 遍历，遇到26时，因为26>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为26；



从 j 遍历，和 i 重合；



将 temp（基准数23）填入arr[i]中。



此时完成算法的第2个步骤，接下来将23左边和右边的子区间分别用以上方法进行排序，直到区间只有一个元素即排序完成。

代码如下：

// Quick_Sort.cpp : Defines the entry point for the application.
// 快速排序算法

#include "stdafx.h"
#include<iostream>
using namespace std;

//快速排序算法(从小到大)
//arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界
void quickSort(int *arr,int begin,int end)
{
	//如果区间不只一个数
	if(begin < end)
	{
		int temp = arr[begin]; //将区间的第一个数作为基准数
		int i = begin; //从左到右进行查找时的“指针”，指示当前左位置
		int j = end; //从右到左进行查找时的“指针”，指示当前右位置
		//不重复遍历
		while(i < j)
		{
			//当右边的数大于基准数时，略过，继续向左查找
			//不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
			while(i<j && arr[j] > temp)
				j--;
			//将右边小于等于基准元素的数填入右边相应位置
			arr[i] = arr[j];
			//当左边的数小于等于基准数时，略过，继续向右查找
			//(重复的基准元素集合到左区间)
			//不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
			while(i<j && arr[i] <= temp)
				i++;
			//将左边大于基准元素的数填入左边相应位置
			arr[j] = arr[i];
		}
		//将基准元素填入相应位置
		arr[i] = temp;
		//此时的i即为基准元素的位置
		//对基准元素的左边子区间进行相似的快速排序
		quickSort(arr,begin,i-1);
		//对基准元素的右边子区间进行相似的快速排序
		quickSort(arr,i+1,end);
	}
	//如果区间只有一个数，则返回
	else
		return;
}
int main()
{
	int num[12] = {23,45,17,11,13,89,72,26,3,17,11,13};
	int n = 12;
	quickSort(num,0,n-1);
	cout << "排序后的数组为：" << endl;
	for(int i=0;i<n;i++)
		cout << num[i] << ' ';
	cout << endl;
	system("pause");
	return 0;
}


运行结果如下：

收起

展开全文

快速排序算法——C/C++

万次阅读 多人点赞 2019-06-12 22:55:14

快速排序 1、算法思想 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 2、实现原理 ...

快速排序
1. 算法思想
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2. 实现原理
2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。

2.2、整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面

默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
循环 2-3 步骤，直到 low=high，该位置就是基准位置。
把基准数据赋给当前位置。

2.3、第一趟找到的基准位置，作为下一趟的分界点。

2.4、递归调用（recursive）分界点前和分界点后的子数组排序，重复2.2、2.3、2.4的步骤。

2.5、最终就会得到排序好的数组。
3. 动态演示


4. 完整代码
三个函数

基准插入函数：int getStandard(int array[],int low,int high)

（返回基准位置下标）

递归排序函数：void quickSort(int array[],int low,int high)

主函数：int main()
#include <stdio.h>
#include <stdlib.h>

void display(int* array, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int getStandard(int array[], int i, int j) {
    // 基准数据
    int key = array[i];
    while (i < j) {
        // 因为默认基准是从左边开始，所以从右边开始比较
        // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
        while (i < j && array[j] >= key) {
            j--;
        }
        // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
        if (i < j) {
            array[i] = array[j];
        }
        // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
        while (i < j && array[i] <= key) {
            i++;
        }
        // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
        if (i < j) {
            array[j] = array[i];
        }
    }
    // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
    // 把基准数据赋给正确位置
    array[i] = key;
    return i;
}

void QuickSort(int array[], int low, int high) {
    // 开始默认基准为 low
    if (low < high) {
        // 分段位置下标
        int standard = getStandard(array, low, high);
        // 递归调用排序
        // 左边排序
        QuickSort(array, low, standard - 1);
        // 右边排序
        QuickSort(array, standard + 1, high);
    }
}

// 合并到一起快速排序
// void QuickSort(int array[], int low, int high) {
//     if (low < high) {
//         int i   = low;
//         int j   = high;
//         int key = array[i];
//         while (i < j) {
//             while (i < j && array[j] >= key) {
//                 j--;
//             }
//             if (i < j) {
//                 array[i] = array[j];
//             }
//             while (i < j && array[i] <= key) {
//                 i++;
//             }
//             if (i < j) {
//                 array[j] = array[i];
//             }
//         }
//         array[i] = key;
//         QuickSort(array, low, i - 1);
//         QuickSort(array, i + 1, high);
//     }
// }

int main() {
    int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
    int size    = sizeof(array) / sizeof(int);

    // 打印数据
    printf("%d \n", size);
    QuickSort(array, 0, size - 1);
    display(array, size);

    // int size      = 20;
    // int array[20] = {0};                 // 数组初始化
    // for (int i = 0; i < 10; i++) {       // 数组个数
    //     for (int j = 0; j < size; j++) { // 数组大小
    //         array[j] = rand() % 1000;    // 随机生成数大小 0~999
    //     }
    //     printf("原来的数组：");
    //     display(array, size);
    //     QuickSort(array, 0, size - 1);
    //     printf("排序后数组：");
    //     display(array, size);
    //     printf("\n");
    // }

    return 0;
}

5. 结果展示
（递归调用，不好展示每次排序结果）


6. 算法分析
时间复杂度：

最好： $O(n log_{2} n)$ 
最坏： $O(n^2)$ 
平均： $O(n log_{2} n)$ 

空间复杂度： $O(n log_{2} n)$ 
稳定性：不稳定

收起

展开全文

用C语言实现快速排序算法

万次阅读 多人点赞 2016-11-04 22:33:13

一、快速排序算法（Quicksort） 1. 定义快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。 2. 基本思想通过一趟排序将要排序的数据分割成独立的两部分，其中...

一、快速排序算法（Quicksort）

1. 定义

快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。



2. 基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3. 步骤

a. 先从数列中取出一个数作为基准数。

b. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

c. 再对左右区间重复第二步，直到各区间只有一个数。

二、C语言实现代码（仅供参考）

 

/*****************************************************
File name：Quicksort
Author：Zhengqijun    Version:1.0    Date: 2016/11/04
Description: 对数组进行快速排序
Funcion List: 实现快速排序算法
*****************************************************/

#include <stdio.h>
#include <stdlib.h>

#define BUF_SIZE 10

/**************************************************
 *函数名：display
 *作用：打印数组元素
 *参数：array - 打印的数组，maxlen - 数组元素个数
 *返回值：无
 **************************************************/
void display(int array[], int maxlen)
{
    int i;

    for(i = 0; i < maxlen; i++)
    {
        printf("%-3d", array[i]);
    }
    printf("\n");

    return ;
}

/************************************
 *函数名：QuickSort
 *作用：快速排序算法
 *参数：
 *返回值：无
 ************************************/
void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j)
        {
            while(i < j && arr[j] >= k)     // 从右向左找第一个小于k的数
            {
                j--;
            }

            if(i < j)
            {
                arr[i++] = arr[j];
            }

            while(i < j && arr[i] < k)      // 从左向右找第一个大于等于k的数
            {
                i++;
            }

            if(i < j)
            {
                arr[j--] = arr[i];
            }
        }

        arr[i] = k;

        // 递归调用
        QuickSort(arr, low, i - 1);     // 排序k左边
        QuickSort(arr, i + 1, high);    // 排序k右边
    }
}

// 主函数
int main()
{
    int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61};
    int maxlen = BUF_SIZE;
    
    printf("排序前的数组\n");
    display(array, maxlen);
    
    QuickSort(array, 0, maxlen-1);  // 快速排序
    
    printf("排序后的数组\n");
    display(array, maxlen);
    
    return 0;
}

 

执行程序后的结果如下所示：



上诉代码结合了我自己对快速排序的看法和理解，仅供参考。

收起

展开全文

排序 C实现快速排序

排序算法系列：快速排序算法

万次阅读 多人点赞 2016-03-01 15:40:07

　本文就来说说交换排序的最后一拍：快速排序算法。之所以说它是快速的原因，不是因为它比其他的排序算法都要快。而是从实践中证明了快速排序在平均性能上的确是比其他算法要快一些，不然快速一说岂不是在乱说？　...

概述
在前面说到了两个关于交换排序的算法：冒泡排序与奇偶排序。

　本文就来说说交换排序的最后一拍：快速排序算法。之所以说它是快速的原因，不是因为它比其他的排序算法都要快。而是从实践中证明了快速排序在平均性能上的确是比其他算法要快一些，不然快速一说岂不是在乱说？

　本文就其原理、过程及实现几个方面讲解一下快速排序算法。
版权声明
著作权归作者所有。

商业转载请联系作者获得授权，非商业转载请注明出处。

作者：Q-WHai

发表日期：2016年3月1日

链接：https://qwhai.blog.csdn.net/article/details/50622744

来源：CSDN

更多内容：分类 >> 算法与数学

目录
文章目录
概述
版权声明
目录
快速排序算法原理原理分析
原理图
算法步骤步骤
过程演示图
逻辑实现
复杂度分析
番外
Ref
GitHub源码下载

快速排序
算法原理
原理分析

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
原理图

算法步骤
步骤
获得待排序数组a
选取一个合适的数字p(一般来说就选取数组或是子数组的第一个元素)作为排序基准
将待排序数组a中比基准p小的放在p的左边，比基准p大的放在p的右边

从第3步获得的两个子数组sub1跟sub2
判断sub1或sub2中是否只有一个元素，如果只有一个元素则返回此元素，否则就将sub1（或是sub2）代回到第1步中继续执行
具体过程可以参见下面的过程图
过程演示图

逻辑实现
/*
     * 排序的核心算法
     * 
     * @param array
     *      待排序数组
     * @param startIndex
     *      开始位置
     * @param endIndex
     *      结束位置
     */
    private void sortCore(int[] array, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        
        int boundary = boundary(array, startIndex, endIndex);
        
        sortCore(array, startIndex, boundary - 1);
        sortCore(array, boundary + 1, endIndex);
    }
    
    /*
     * 交换并返回分界点
     * 
     * @param array
     *      待排序数组
     * @param startIndex
     *      开始位置
     * @param endIndex
     *      结束位置
     * @return
     *      分界点
     */
    private int boundary(int[] array, int startIndex, int endIndex) {
        int standard = array[startIndex]; // 定义标准
        int leftIndex = startIndex; // 左指针
        int rightIndex = endIndex; // 右指针
        
        while(leftIndex < rightIndex) {
            while(leftIndex < rightIndex && array[rightIndex] >= standard) {
                rightIndex--;
            }
            array[leftIndex] = array[rightIndex];
            
            while(leftIndex < rightIndex && array[leftIndex] <= standard) {
                leftIndex++;
            }
            array[rightIndex] = array[leftIndex];
        }
        
        array[leftIndex] = standard;
        return leftIndex;
    }

复杂度分析
排序方法
             时间复杂度
             空间复杂度
             稳定性
             复杂性
         
平均情况
             最坏情况
             最好情况
         
快速排序
             O(nlog₂n)
             O(n²)
             O(nlog₂n)
             O(log₂n)
             不稳定
             较复杂
         

　这里我们可以做一些关于复杂度的推理。
　如果我们在选取基准p的时候，每次选取的都是当前数组中最小的一个元素，那么每次划分都只是让数组中的元素少1（被筛选出来的那个元素当然有序），这样一来就需要反复遍历数组导致复杂度变成了O(n²)。
　如果我们在选取基准p的时候，每次选取的都是当前数组中最中间的一个元素（是中位数，而不是元素位置上的中间），那么每次划分都把当前数组划分成了长度相等的两个子数组，这样一来复杂度变成了O(nlog₂n)。
番外
对于基准元素的选取，也可以采用随机数选取的方式
如果要按照元素在位置上的中间来选取基准元素，还可以将中间位置上的元素与第一个元素进行对换
Ref
《算法导论 （第3版）》
《编程珠玑 （第2版）》
GitHub源码下载
https://github.com/qwhai/algorithms-sort

收起

展开全文

算法

图解快速排序算法
千次阅读 2018-05-11 11:22:19
快速排序算法
收起

排序方法	时间复杂度			空间复杂度	稳定性	复杂性
	平均情况	最坏情况	最好情况
快速排序	O(nlog₂n)	O(n²)	O(nlog₂n)	O(log₂n)	不稳定	较复杂

快速排序算法

快速排序算法——C/C++

快速排序

1. 算法思想

2. 实现原理

3. 动态演示

4. 完整代码

5. 结果展示

6. 算法分析

用C语言实现快速排序算法

排序算法系列：快速排序算法

概述

版权声明

目录

文章目录

快速排序

算法原理

原理分析

原理图

算法步骤

步骤

过程演示图

逻辑实现

复杂度分析

番外

Ref

GitHub源码下载

图解快速排序算法

快速排序算法