java 数据结构与算法 ——快速排序法

简介: java 数据结构与算法 ——快速排序法

快速排序法:


顾名思议,快速排序法是实践中的一种快速的排序算法,在c++或对java基本类型的排序中特别有用。它的平均运行时间是0(N log N)。该算法之所以特别快,主要是由于非常精练和高度优化的内部循环。

快速排序是对冒泡法的一种改进。通过一趟排序将要排序的的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有的数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


示意图:

d4e8fa1680fb48e2aa458fe4d68f4a5f.png

8541bb69158a45bdab9923d53067a809.png

这里 定义最左边元素 为left 最右边元素为right

p 元素的值 就是 2对应的索引 0 加上 5对应的索引 7 之和 除以2 得到 索引为3 对应的元素7

用左边大于 7的数跟右边小于7的数进行 交换位置 一直进行 并且 中间的p也要一直变化位置

直到 排完

7d34fdc5d0ad4a16a2be26107d26d284.png


代码实现:

import java.util.Arrays;
public class kuaisu {
    public static void main(String[] args) {
        int arrays[]=new int[]{2,9,4,7,3,3,6,5};
        sort(arrays,0,arrays.length-1);
        System.out.println(Arrays.toString(arrays));
    }
  public  static  void  sort(int arrays[],int left,int right){
        int l=left ;//给定下标
        int r=right;//给定下标
        int temp; //定义一个变量 作为中间值 交换 左右两边的元素位置
        int pivot=arrays[(left+right)/2];//中间值
        while(l<r){
            //在左边查找小于中间值得元素
            while(arrays[l]<arrays[pivot]){
                l++;
            }
            //同理在右边查找大于中间值得元素
            while(arrays[r]>arrays[pivot]){
                r--;
            }//直到左边元素大于右边元素就结束
            if(l>=r){
                break;
            }
            temp=arrays[l];
            arrays[l]=arrays[r];
            arrays[r]=temp;
            //交换完arrays[l]=pivot
            if(arrays[l]==pivot){
                r--;
            }
            if(arrays[r]==pivot){
                l++;
            }
            if(r==l){ //要让左边元素 往左边移 右边元素往右边移 错开
                l++;
                r--;
            } //对左边进行递归
            if(left<r){
                sort(arrays,left,r);
            }//对右边进行递归
            if(right>l){
                sort(arrays,l,right);
            }
        }
    }
}

控制台输出结果 如下:


9ba6d9c765d84902861c903ab67ce261.png

相关文章
|
22天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
59 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
12天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
24 1
|
14天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
56 2
|
14天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
45 2
|
3天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
11天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
18 6
|
12天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
23 1
|
20天前
|
存储 算法 Java
Java常用的数据结构
【10月更文挑战第3天】 在 Java 中,常用的数据结构包括数组、链表、栈、队列、树、图、哈希表和集合。每种数据结构都有其特点和适用场景,如数组适用于快速访问,链表适合频繁插入和删除,栈用于实现后进先出,队列用于先进先出,树和图用于复杂关系的表示和查找,哈希表提供高效的查找性能,集合用于存储不重复的元素。合理选择和组合使用这些数据结构,可以显著提升程序的性能和效率。
|
27天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
28 6
|
27天前
|
Java 语音技术 容器
java数据结构泛型
java数据结构泛型
26 5