【数据结构】排序算法(二)之交换排序之快速排序(QuickSort)

前端之家收集整理的这篇文章主要介绍了【数据结构】排序算法(二)之交换排序之快速排序(QuickSort)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

上一次学习了【【数据结构】排序算法(一)之直接插入排序,冒泡排序】今天重新学习了一下快速排序

快速排序是是属于交换排序的范畴,另外一种的交换排序的代表是冒泡排序(上面有冒泡排序的链接地址

快排的基本思路其实还是挺简单的:我们从需要排序的数组从任取一个当做分界值(暂时称作n),把所有比n小的值放在n的左边,把大的放在n的右边。这样进行遍历一遍下来,就可以形成左右两个序列,左边的数据都比右边的小,然后左右两边的序列分别进行递归的遍历。直到每一个字序列只剩下一个元素的时候,排序结束。。。。

首先我们来看看遍历第一趟会做哪些事情:

①选择一个分界点;

②:将比分界点小的数放在分界点的左边

③:将比分界点大的数放在分界点的右边


实现的步骤如下:

1:先定义一个变量i,使用这个变量从左边第一个开始向右进行遍历,找出大于分界点的值的那个索引,并且使用i变量记录下来

2:定义一个变量j,使用这个变量从右边第一个开始向左进行遍历,找出小于分界点的值的那个索引,并且使用j变量记录下来

3:如果比较发现i<j,那就交换分别有i,j标记索引相对应的值;

重复上面步骤,一直到i>=j的时候,可以判断分界点左边的值都小于分界点,同理分界点右边的值都大于分界点

到最后的时候还必须把分界点的值和j索引处的值进行交换....


下面是代码:

package com.jiangqq.quicksort;

/*=======================================
 * 本例子是演示使用Java进行快速排序(快速排序属于选择排序之一,当时属于选择排序的另一种排序是冒泡排序)
 * 这里默认使用int[]类型的数组
 * 
 * @author:jiangqq
 * @time:2012/03/14  22:11
 * ======================================
 */
public class QuickSort {

	/**
	 * 将数据组根据其中的索引i与j进行交换数据
	 * 
	 * @param data
	 * @param i
	 * @param j
	 */
	private static void swap(int[] data,int i,int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	/**
	 * 根据传入的a和b的值进行比较大小,如果a大于b,返回1,否则返回-1,如果相等返回0
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int compare(int a,int b) {
		int temp = a - b;
		if (temp > 0) {
			return 1;
		}
		if (temp < 0) {
			return -1;
		}
		if (temp == 0) {
			return 0;
		}
		return 0;
	}

	/**
	 * 根据传入的数组打印出数组
	 * 
	 * @param data
	 */
	private static void printDate(int[] data) {
		System.out.print("[");
		for (int i = 0; i < data.length; i++) {
			if (i != data.length - 1) {
				System.out.print(data[i] + ",");
			} else {
				System.out.print(data[i]);
			}
		}
		System.out.print("]");
	}

	/**
	 * 进行快速排序,排序满足,所有小于分界点的都在左边,所有大于分界点的都在右边
	 * 
	 * @param data
	 * @param start
	 * @param end
	 */
	public static void subSort(int[] data,int start,int end) {
		if (start < end)// 此刻开始排序
		{
			// 默认把数组的第一个当做分界值
			int dividing = data[start];
			//i是默认从左边开始进行搜索
			int i = start;
			//j是默认从右边开始进行搜索
			int j = end+1;
			while (true) {
				while (i < end && (compare(data[++i],dividing) <= 0))
					;
				while (j > start && (compare(data[--j],dividing) >= 0))
					;
				if (i < j) {
					swap(data,i,j);
				} else {
					break;
				}
			}
			swap(data,start,j);
			subSort(data,j - 1);
			subSort(data,j + 1,end);
		}
	}

	private static void quickSort(int data[]) {
		subSort(data,data.length-1);
	}

	public static void main(String[] args) {
		int[] data = new int[] { 9,15,21,-67,30,13 };
		System.out.println("快速排序之前的数组如下:============================");
		printDate(data);
		// 调用快排的方法
		quickSort(data);
		
		System.out.println("\n快速排序之后的数组如下:============================");
		printDate(data);
	}
}


运行结果:



最后提一下,这种排序的方法速度效率是挺好,空间复杂度O(log2n),但是是不稳定的排序算法...

原文链接:https://www.f2er.com/datastructure/383252.html

猜你在找的数据结构相关文章