【数据结构】排序算法（二）之交换排序之快速排序(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)，但是是不稳定的排序算法...

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!