欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

笨办法学数据结构 快速排序算法实现

程序员文章站 2022-06-17 19:06:16
快速排序法介绍:快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列示意图:算法讲解:想设置一个初始数组,最左边设为left,最右边设为right,将最右边的数设置为基准数并命名为key,第一次排序时比3大的数移到3右边,比3小的数移到右边移动左右指针,找到比3大和比3....

快速排序法介绍:

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

示意图:

笨办法学数据结构  快速排序算法实现

算法讲解:

想设置一个初始数组,最左边设为left,最右边设为right,将最右边的数设置为基准数并命名为key,第一次排序时比3大的数移到3右边,比3小的数移到右边

 笨办法学数据结构  快速排序算法实现

移动左右指针,找到比3大和比3小的数,并交换位置 

笨办法学数据结构  快速排序算法实现

移动完位置后继续重复上述操作

笨办法学数据结构  快速排序算法实现

笨办法学数据结构  快速排序算法实现

当左右指针重合时,结束循环并交换key与重合数的位置

笨办法学数据结构  快速排序算法实现

交换位置之后将重合数的左右两边利用递归再次继续排序

代码演示:



import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int arry[] = new int[8];
		for (int i = 0; i < arry.length; i++) {
			arry[i] = (int) (Math.random() * 8000);
		}
		System.out.println(Arrays.toString(arry));
		quickSort(arry, 0, arry.length - 1);
		System.out.println("排序后数据");
		System.out.println(Arrays.toString(arry));
	}

	public static void quickSort(int arry[], int left, int right) {
	
		if (arry.length == 0 || arry == null) {
			return;
		}
		if (left > right) {
			return;
		}
		int l = left;
		int r = right;
		int key = arry[left];
		int temp = 0;
		while (l != r) {
			while (arry[r] >= key && l < r) {
				r--;
			}
			
			while (arry[l] <= key && l < r) {
				l++;
			}
			
			temp = arry[l];
			arry[l] = arry[r];
			arry[r] = temp;
		}
		arry[left] = arry[l];
		arry[l] = key;
		
	
		quickSort(arry, l + 1, right);
		quickSort(arry, left, r - 1);
	}
}

 

本文地址:https://blog.csdn.net/weixin_45829957/article/details/107691568