C/C++ 快速排序_代码007(未授权)

本文介绍: 一、引言快速排序的思想——分治一、引言快速排序是对冒泡排序的一种改进。它的基本思想在于划分，首先选一个基准 x，让x的左边都小于x，让x的右边都大于 x。然后通过递归，一直将数组分成两个或一个元素。二、讲解1、步骤1、将确定分界点。2、调整范围——让基准 x的左边都小于x，让x的右边都大于x。3、递归分治。如果arr 数组为：【0，1】基准点为左边界。因为i先自增，ar r[0]==0,退出循环.。j先自减，ar r[j]&g t;0,继续进入循环，j–，ar r[j]==0,退出循环。

快速排序的思想——分治

一、引言

二、讲解

1、步骤

#include&lt;iostream&gt;
using namespace std;
#include&lt;cstdio&gt;
const int N = 1e5 + 5;
int arr[N], n;
void quick_sort(int arr[], int l, int r) {
    if (l &gt;= r) {
        return;
    }
    //基准x是arr数组的左边界
    int i = l - 1, j = r + 1, x = arr[l];
    while (i &lt; j) {
        do {
            i++;
        } while (arr[i] < x);
        do {
            j--;
        } while (arr[j] &gt; x);
        if (i < j) {
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    //这块要配合着基准x为arr的左边界，下边的j不能换成i
    //如果要换成i的话，基准x也要跟着变
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}
int main() {
    scanf("%d", &amp;n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &amp;arr[i]);
    }
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

#include<iostream&gt;
using namespace std;
#include<cstdio>
const int N = 1e5 + 5;
int arr[N], n;
void quick_sort(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }
    int i = l - 1, j = r + 1, x = arr[r];
    while (i < j) {
        do {
            i++;
        } while (arr[i] < x);
        do {
            j--;
        } while (arr[j] > x);
        if (i < j) {
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    quick_sort(arr, l, i-1);
    quick_sort(arr, i, r);
}
int main() {
    scanf("%d", &amp;n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &amp;arr[i]);
    }
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

#include<iostream>
using namespace std;
#include<cstdio>
const int N = 1e5 + 5;
int arr[N], n;
void quick_sort(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }
    int i = l - 1, j = r + 1, x = arr[(l+r)/2];
    while (i < j) {
        do {
            i++;
        } while (arr[i] < x);
        do {
            j--;
        } while (arr[j] > x);
        if (i < j) {
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j+1, r);
}
int main() {
    scanf("%d", &amp;n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &amp;arr[i]);
    }
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}