栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序之快速排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序之快速排序

排序之快速排序

文章目录
  • 排序之快速排序
  • 前言
  • 快速排序定义和时间复杂度分析
    • 定义
    • 算法复杂度
    • 快速排序的优越性
  • 解题思路及实例解答
    • 解题思路
  • Java实现
    • 1.Java代码
      • 升序排序
      • 快速排序
      • 随机化快速排序(改进版)
      • 改进效果
    • 2.代码运行示例:
      • 样例输入:
      • 样例输出:
  • 总结


前言

本博客仅做学习笔记,如有侵权,联系后即刻更改

科普:快速排序


快速排序定义和时间复杂度分析
定义

是对冒泡排序算法的一种改进
快速排序算法的性能取决于划分的对称性

算法复杂度

(1)最坏情况:O(n^2)
√
(2)最好情况:O(nlogn)
√
(3)一般情况:O(nlogn)
√
平均时间复杂度:T(n) = O(nlogn)

快速排序的优越性

数据量越大,节省的计算资源越多!

解题思路及实例解答
解题思路

数据分区:一部分比另一部分小
递归排序:递归处理两部分

Java实现 1.Java代码

代码如下:

//主函数
import java.util.Scanner;

import static java.lang.Math.random;

public class quick_sort_main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    while (scanner.hasNext()) {
      int n = scanner.nextInt();
      int[] sort = new int[n];
      for (int i = 0; i < n; i++) {
        sort[i] = scanner.nextInt();
      }
//1.
//      quick_sort(0,n-1,sort);
//2.
      quickSort(sort, 0 , n-1);
//3.生成随机数
//      randomizedQuickSort(sort ,0 ,n-1);
      for (int i = 0; i < n; i++) {
          System.out.print(sort[i]+" ");
   		  }
   		}
	 }
  }
>交换函数
 static void swap(int []sort,int i,int j){
    int middle = sort[i];
    sort[i] = sort[j];
    sort[j] = middle;
  }
升序排序

这个可以实现排序,但是不知道是不是快速排序,有知道的可以评论留言告诉我一下,不甚感激

  static void quick_sort(int low,int height,int[] sort){
    if(low > height)
      return ;
    int i, j,temp,t;
    i = low;
    j = height;
    temp = sort[low];

    while (i
      //从左边找比基准数小的第一个数
      while (sort[j] >= temp && i < j) j--;
      //从右边找比基准数大的第一个数
      while (sort[i] <= temp && i < j) i++;
      //满足条件,交换sort[i]和sort[j]
      if (i < j) swap(sort,i,j);
    }

    sort[low] = sort[i];
    sort[i] = temp;
    quick_sort(low,j-1,sort);
    quick_sort(j+1,height,sort);
  }
快速排序
  //2.分区函数
static int partition(int sort[], int p, int q){
    int x = sort[p];
    int i = p;
    for(int j = p+1; j <= q; j++){
      if(sort[j] <= x){
        i++;
        swap(sort, i , j);
      }
    }
    swap(sort,p,i);
    return i;
  }
  
  //2.快速排序
  static void quickSort(int []sort, int p ,int q){
    if(p < q){
      int r = partition(sort, p ,q);
      quickSort(sort, p ,r-1);
      quickSort(sort, r+1, q);
    }
  }
随机化快速排序(改进版)

快速排序算法的性能取决于划分的对称性
√
通过修改算法Partition,可以设计出采用随机选择策略的快速排序算法
√
在A[p..q]中随机选出一个元素作为划分基准

 //3.随机数产生

  static int rand(int p, int q){
    return (int) (random()%(q-p+1) + p);
  }
  
  //3.分区函数

```java
  static int randomizedPartition(int []sort, int p, int q){
    int r = rand(p , q);
    swap(sort, p , r);
    int i = partition(sort, p, q);
    return i;
  }

  //3.快速排序
 
 static void randomizedQuickSort(int[] sort ,int p ,int q){
    if (p < q) {
      int r = randomizedPartition(sort , p, q);
      randomizedQuickSort(sort ,p ,r-1);
      randomizedQuickSort(sort ,r+1 ,q);
    }
  }
改进效果

随机化快速排序时间复杂度:T(n)= O(nlogn)


2.代码运行示例:
样例输入:

6 1 8 6 5 3 4
5 12 42 2 5 8

样例输出:

1 3 4 5 6 8
2 5 8 12 42

总结

时间复杂度:
平均时间复杂度:T(n) = O(nlogn)
最坏情况:O(n^2)
经过随机数优化后,随机化快速排序时间复杂度:T(n)= O(nlogn)

小小励志

有些事你现在不做,一辈子都不会做了。
如果你想做一件事,全世界都会为你让路。
《搭车去柏林》

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981252.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号