Table of Contents
经典算法学习——快速排序
Home Backend Development PHP Tutorial 经典算法学习——快速排序_PHP教程

经典算法学习——快速排序_PHP教程

Jul 12, 2016 am 08:54 AM
algorithm classic

经典算法学习——快速排序

快速排序应该算是在面试笔试中最常用的算法了,各位面试官都非常喜欢。排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,其中的思想也是用了分治法和递归的思想。示例代码上传到:https://github.com/chenyufeng1991/QuickSort

算法的基本思想是:

(1)先从数列中取出一个数作为基准数(常常选第一个数);

(2)分区过程,比这个数大的数放到它的右边,小于或等于的数全放到它的左边;

(3)再对左右区间重复第二步,直到每个区间只有一个数位置,即左边界下标等于右边界下标;

简化描述为:

1.i= L, j=R,基准数即为a[i],保存起来;

2.j--,由后向前找比它小的数,找到后将此数放到a[i]中;

3.i++,由前向后找比它大的数,找到后将此数填入到a[j]中;

4.递归执行2,3两步,直到i==j,最后将基准数填入a[i]中;

具体代码实现如下:

//
//  main.c
//  QuickSort
//
//  Created by chenyufeng on 16/1/27.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include <stdio.h>

int *quickSort(int arr[],int l,int r);
void quickSort02(int *arr,int l,int r);

int main(int argc, const char * argv[]) {

    int numArr[5] = {3,6,0,9,4};

    //使用指针返回数组,返回的其实是数组的头指针;
    /**
     *  使用返回指针;
     */

//    int *retArr;
//    retArr = quickSort(numArr, 0, 4);
//    for (int i = 0; i < 5; i++) {
//        //取数组值
//        printf("%d ",*(retArr + i));
//    }


    /**
     *  直接传递引用,比较方便;
     */
    quickSort02(numArr, 0, 4);
    for (int i = 0; i < 5; i++) {
        printf("%d ",numArr[i]);
    }
}

int *quickSort(int arr[],int l,int r){
    //当左右指针相等的时候直接返回;
    if (l < r) {
        //此时的x就是基准值;
        int i = l,j = r,x = arr[l];

        //下面的while循环表示一次分治,也就是进行一次排序;
        while (i < j) {
            //先从基准值右侧找出小于基准的值;
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                //交换顺序,i++;
                arr[i++] = arr[j];
            }

            //从基准值左侧找出大于基准的值;
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                //交换顺序,j--;
                arr[j--] = arr[i];
            }
        }
        //把基准值放入arr[i]位置;
        arr[i] = x;
        //递归,左右两侧分别进行快排;
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
    return arr;
}

void quickSort02(int *arr,int l,int r){
    //当左右指针相等的时候直接返回;
    if (l < r) {
        //此时的x就是基准值;
        int i = l,j = r,x = arr[l];

        //下面的while循环表示一次分治,也就是进行一次排序;
        while (i < j) {
            //先从基准值右侧找出小于基准的值;
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                //交换顺序,i++;
                arr[i++] = arr[j];
            }

            //从基准值左侧找出大于基准的值;
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                //交换顺序,j--;
                arr[j--] = arr[i];
            }
        }
        //把基准值放入arr[i]位置;
        arr[i] = x;
        //递归,左右两侧分别进行快排;
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
}</stdio.h>
Copy after login

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1119561.htmlTechArticle经典算法学习——快速排序 快速排序应该算是在面试笔试中最常用的算法了,各位面试官都非常喜欢。排序效率在同为O(N*logN)的几种排序方...
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance Mar 26, 2024 pm 12:41 PM

CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance

Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Jun 03, 2024 pm 01:25 PM

Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions

Explore the underlying principles and algorithm selection of the C++sort function Explore the underlying principles and algorithm selection of the C++sort function Apr 02, 2024 pm 05:36 PM

Explore the underlying principles and algorithm selection of the C++sort function

Practice and reflections on Jiuzhang Yunji DataCanvas multi-modal large model platform Practice and reflections on Jiuzhang Yunji DataCanvas multi-modal large model platform Oct 20, 2023 am 08:45 AM

Practice and reflections on Jiuzhang Yunji DataCanvas multi-modal large model platform

Improved detection algorithm: for target detection in high-resolution optical remote sensing images Improved detection algorithm: for target detection in high-resolution optical remote sensing images Jun 06, 2024 pm 12:33 PM

Improved detection algorithm: for target detection in high-resolution optical remote sensing images

Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Mar 22, 2024 pm 10:10 PM

Can artificial intelligence predict crime? Explore CrimeGPT's capabilities

PHP algorithm analysis: efficient method to find missing numbers in an array PHP algorithm analysis: efficient method to find missing numbers in an array Mar 02, 2024 am 08:39 AM

PHP algorithm analysis: efficient method to find missing numbers in an array

Application of algorithms in the construction of 58 portrait platform Application of algorithms in the construction of 58 portrait platform May 09, 2024 am 09:01 AM

Application of algorithms in the construction of 58 portrait platform

See all articles