快速排序(整数)的C语言代码和JAVA代码

一、问题描述

我们目前有一些数据,这些数据都是整数,然后我们现在需要做的就是把这些数据按照小到大排一下,然后输出出来。

二、问题的解决办法

首先确认一下分界点,我们常见的分界点是第一个点,第二个点,中间的一个点;

然后我们调整一下范围,也就说所有小于等于某个点的值在左半边,大于等于某个点的值在右半边。

递归处理左右两端。

案例如下:

我们首先手头有一些数据,这些数据我们为了好排序,可以把他们都放在数组当中,这样每个数据都有一个下标了,也就确定了它们的位置。如下:

快速排序(整数)的C语言代码和JAVA代码

 

 

 这个时候我们选好了分界值,如上所示,为8。下一步我们就进行位移:

快速排序(整数)的C语言代码和JAVA代码

 

 快速排序(整数)的C语言代码和JAVA代码

 

 由于8=8,所以i静止不动,9>8,这就使得j--;如下:

快速排序(整数)的C语言代码和JAVA代码

 

 三、代码实现:

C:

#include<stdio.h>
const int N=1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r){
    if(l>=r) return ;//判定边界

    int x=q[l],i=l-1,j=r+1;
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j){
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
        }
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

    for(int i=0;i<n;i++) printf("%d ",q[i]);
    return 0;
}

JAVA:

import java.util.Scanner;;
public class quick_sort {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[100010];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        quick_s(arr,0,n-1);
        for(int i=0;i<n;i++){
            System.out.printf("%d ",arr[i]);
        }
    }
    public static void quick_s(int q[],int l ,int r) {
        int i=l-1;
        int j=r+1;
        int x=q[l+r>>1];
        if(l>=r) return;
        while(i<j){
            do i++;while(x>q[i]);
            do j--;while(x<q[j]);
            if(i<j){
                int t=q[i];
                q[i]=q[j];
                q[j]=t;
            }
            quick_s(q, l, j);
            quick_s(q, j+1, r);
        }
    }
}

 

原文链接:https://www.cnblogs.com/TomHard/p/17255547.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:快速排序(整数)的C语言代码和JAVA代码 - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • Python中的函数式编程:不可变的数据结构

    Python是一门支持函数式编程的语言。相比于传统的命令式编程,函数式编程更加强调数据的不可变性。本文将介绍如何在Python中使用不可变的数据结构实现函数式编程。 什么是不可变的数据结构? 不可变数据结构是指一旦创建就无法改变的数据结构。在Python中,元组(tuple)是一个典型的不可变数据结构。以下是一个创建元组的示例代码: a_tuple = (1…

    数据结构 2023年5月17日
    00
  • C语言顺序表的基本结构与实现思路详解

    C语言顺序表的基本结构与实现思路详解 什么是顺序表 顺序表,顾名思义,就是使用连续的存储空间来存储数据元素的线性表。在顺序表中,每一个数据元素都占用一个连续的存储单元,这些存储单元在物理上连续存放,因此,顺序表实际上就是由一个存储数据元素的数组和记录该数组大小的变量组成的。 顺序表的基本结构 顺序表的定义 “`c #define MAXSIZE 100 /…

    数据结构 2023年5月17日
    00
  • Python三数之和的实现方式

    Python三数之和的实现方式 三数之和是一道经典的算法问题,其目标是在一个数组中找到三个数,使它们为0。本文将介绍两种Python实现三数之和的方法。 方法一:暴力枚举 最简单的方法是使用重循环枚举所有可能的三元组,并检查它们的和是否为0。这种方法的时间复杂度为O(n^3),不用于大型数组。 下面是一个示例,用于演示如何使用暴力枚举实现三数之和。 def …

    python 2023年5月14日
    00
  • 使用Python进行数独求解详解(一)

    下面是详细讲解“使用Python进行数独求解详解(一)”的完整攻略。 数独简介 数独是一种逻辑游戏,玩家需要在9×9的网格填入数字,使得每行、每列和每个3×3的网格中的数字都是1-9的不重复数字。数独难度分为简单、中等和困难三个等级。 数独求解算法 数独求解算法的基本思路是使用回溯法,从左到右、从上到下依次填入数字如果填入的数字与已有数字冲突,则回溯到上一个…

    python 2023年5月14日
    00
  • python实现CSF地面点滤波算法原理解析

    Python实现CSF地面点滤波算法原理解析 本文将介绍如何使用Python实现CSF(Curvature Scale Space)地面点滤波算法。我们将介绍CSF法的原理和实现步骤,并提个示例,分别演示如何使用Python实现简单和复杂的地面点滤。 CSF算法原理 CSF算法是一种于曲率尺度空间的地面点滤波算法。该算法通过计算点云曲率来识别地面点,并使用曲…

    python 2023年5月14日
    00
  • Python实现的凯撒密码算法示例

    以下是关于“Python实现的凯撒密码算法示例”的完整攻略: 简介 凯撒密码是一种简单的加密算法,它通过将明文中的每个字母按照一定的偏移量进行替换,从而得到密文。在本教程中,我们将介绍如何使用Python实现凯撒密码算法,并提供两个示例说明。 实现凯撒密码算法 以下是使用Python实现凯撒密码算法的代码: def caesar_cipher(text, s…

    python 2023年5月14日
    00
  • Python实现字符串的逆序 C++字符串逆序算法

    以下是关于“Python和C++实现字符串逆序算法”的完整攻略: 简介 字符串逆序是一种常见的字符串操作,它可以将字符串中的字符顺序颠倒过来。Python和C++都提供了多种方法来实现字符串逆序。本教程将介绍如何使用Python和C++实现字符串逆序算法,并提供两个示例说明。 Python实现 1.使用切片 Python中可以使用切片来实现字符串逆序。可以使…

    python 2023年5月14日
    00
  • 详解小白之KMP算法及python实现

    详解小白之KMP算法及Python实现 KMP算法是一种字符串匹配算法,它可以在O(n+m)的时间复杂度内解决字符串匹配问题。本文将详细讲解KMP算法的原理、实现过程和代码实现,并提供两个示例说明。 算法原理 KMP算法的基本思想是利用已知信息,尽可能减少匹配的次数。具体实现过程如下: 一个next数组,用于存储模式串中每个字符前面的最长公共前后缀长度。 遍…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部