【快速排序代码】记录:Java & C++

简介: 【快速排序代码】记录:Java & C++

快排思想


快速排序的基本思想是:通过一次排序将要排序的数据分成两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,直到有序。


C++


#include<iostream>
using namespace std;
void print(int a[], int n)
{  
    for(int j= 0; j<n; j++)
  {  
           cout<<a[j] <<"  ";  
        }  
    cout<<endl;  
}  
void quickSort(int a[], int low ,int high)
{
  if(low<high)  //判断是否满足排序条件,递归的终止条件
  {
    int i = low, j = high;   //把待排序数组元素的第一个和最后一个下标分别赋值给i,j,使用i,j进行排序;
    int x = a[low];    //将待排序数组的第一个元素作为哨兵,将数组划分为大于哨兵以及小于哨兵的两部分                                   
    while(i<j)  
    {
      while(i<j && a[j] >= x) j--;  //从最右侧元素开始,如果比哨兵大,那么它的位置就正确,然后判断前一个元素,直到不满足条件
      if(i<j) a[i++] = a[j];   //把不满足位次条件的那个元素值赋值给第一个元素,(也即是哨兵元素,此时哨兵已经保存在x中,不会丢失)并把i的加1
      while(i<j && a[i] <= x) i++; //换成左侧下标为i的元素开始与哨兵比较大小,比其小,那么它所处的位置就正确,然后判断后一个,直到不满足条件
      if(i<j) a[j--] = a[i];  //把不满足位次条件的那个元素值赋值给下标为j的元素,(下标为j的元素已经保存到前面,不会丢失)并把j的加1
    } 
          a[i] = x;   //完成一次排序,把哨兵赋值到下标为i的位置,即前面的都比它小,后面的都比它大
    quickSort(a, low ,i-1);  //递归进行哨兵前后两部分元素排序 , low,high的值不发生变化,i处于中间
    quickSort(a, i+1 ,high);
  }
}
int main()
{  
    int a[10] = {8,1,9,7,2,4,5,6,10,3};  
    cout<<"初始序列:";  
    print(a,10);  
    quickSort(a,0,9);  
    cout<<"排序结果:";  
    print(a,10);  
    system("pause"); 
} 


Java


package com.leetcode.www;
import java.util.*;
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr,0,arr.length - 1);
        return Arrays.copyOf(arr, k);
    }
    public void quickSort(int[] arr,int l ,int r){
        if(l > r)
            return;
        int i = l,j = r;
        while(i < j){
            while(i < j && arr[j] >= arr[l])
                j--;
            while(i < j && arr[i] <= arr[l])
                i++;
            swap(arr,i,j);
        }
        swap(arr,i,l);
        quickSort(arr,l,i - 1);
        quickSort(arr,i + 1,r);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        Solution solution=new Solution();
        int []a = {8,1,9,7,2,4,5,6,10,3};
        System.out.println("初始队列:");
        System.out.println(Arrays.toString(a));
        solution.getLeastNumbers(a,10);
        System.out.println("排序结果:");
        System.out.println(Arrays.toString(a));
    }
}


相关文章
|
9天前
|
Java 程序员 API
Java中的Lambda表达式:简化你的代码
【7月更文挑战第10天】Lambda表达式,这一Java 8的闪亮特性,为开发者提供了一种更为简洁、灵活的编程方式。本文将探讨Lambda表达式如何优化代码结构,提升开发效率,以及在实际项目中应用的一些实例。我们将从基础语法入手,逐步深入到高级用法,最后讨论其性能影响,旨在帮助读者全面理解并有效利用Lambda表达式。
34 20
|
2天前
|
存储 缓存 JavaScript
|
10天前
|
监控 Java Maven
使用AspectJ实现Java代码的运行时织入
使用AspectJ实现Java代码的运行时织入
|
15天前
|
缓存 算法 安全
|
2天前
|
SQL Java 数据处理
实时计算 Flink版产品使用问题之使用MavenShadePlugin进行relocation并遇到只包含了Java代码而未包含Scala代码,该怎么办
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
|
8天前
|
Java 编译器 API
Java中的Lambda表达式:简化代码,提升性能
在Java 8中,Lambda表达式的引入为开发者提供了一种更加简洁、灵活的编程方式。本文将深入探讨Lambda表达式的概念、语法、使用场景及其在Java中的应用示例,帮助读者更好地理解和掌握这一强大工具,从而优化代码结构,提高开发效率。
|
11天前
|
监控 Java Maven
使用AspectJ实现Java代码的运行时织入
使用AspectJ实现Java代码的运行时织入
|
14天前
|
Java Linux Shell
Linux软件安装和部署Java代码
Linux软件安装和部署Java代码
21 0
|
14天前
|
IDE Java 持续交付
Java中的代码质量检查与自动化工具
Java中的代码质量检查与自动化工具
|
14天前
|
编译器 程序员 C++
【C++高阶】掌握C++多态:探索代码的动态之美
【C++高阶】掌握C++多态:探索代码的动态之美
18 0

热门文章

最新文章