快速排序

 

假设一个数

 

66 8 5 44 9 77 2 33 41 15 42 69

 

现在随机挑选一个键值，假设我们选到的是41 ，把41 作为key 值存在。设左部序列标为i, 右部序列标为j, 将这个数列升序排序。

 

从左边开始，66 比41 来得大，两者交换，现在key 值41 在第一位，i 指向第一位，

 

得到的序列为：41 (I) 8 5 44 9 77 2 33 66 15 42 69(J)

 

轮到右部，找到第一个比41 小的数为45 者交换，现在i 指向第一位，j 指向右第三位，key 值在第8 位，即跟j 重合。

 

得到的序列为： 15(I) 8 5 44 9 77 2 33 66 41(J) 42 69

 

继续比i ，44 比41 来得大，两者交换，现在i 指向第四位，j 指向右数第三位，i 跟key 重合，

 

得到的序列为：15 8 5 41 （i ） 9 77 2 33 66 44 (j) 42 69;

 

 

j 继续往下移，33 比41 来得小，两者交换，现在i 指向第四位，j 指向右数第六位，key 与是重合，

 

得到的序列为： 15 8 5 33 （i ） 9 77 2 41(j) 66 44 42 69

 

i 往下，77 比41 来得大, 交换

 

得到的序列为：15 8 5 33 9 41 （i ） 2 77(j) 66 44 42 69

 

j 往下,2 比41 小

 

得到的序列为： 15 8 5 33 9 2 （i ） 41(j) 77 66 44 42 69

 

i 往下，i 与j 重合

第一轮排序结束，得到序列 15 8 5 33 9 2 41 77 66 44 42 69

 

现在把序列为分两部分，左部为 15 8 5 33 9 2

右部为 41 77 66 44 42 69

同样排序

 

得最后排序结果： 2 5 8 9 15 33 41 42 44 66 69 77

 

 

java实现如下：

    Sort接口：

 

package com.javaeye.rsrt;

public interface Sort {
	
	/**
	 * 供程序使用的快速排序的接口
	 * @param num 要进行排序的数序
	 * @return 排好序的数列
	 */
	public int[] BeginSort(int[] num);

}

 QuickSort类：

 

package com.javaeye.rsrt;

/**
 * 
 * @author nishiting
 * 
 * 原理：要求将传进来的数列进行排序，快速排序是冒泡法的一个改进版，先通过第一轮排序把数列分为
 * 两部分，一部分比关键值小，一部分比关键值大，然后将分开的两部分再进行排序，直到排序结束为止。
 *
 */
public class QuickSort implements Sort {
	

	@Override
	public int[] BeginSort(int[] num){
		
		Sort(num,0,num.length-1);
		
		System.out.print("num:");
		for(int i = 0;i<num.length;i++){
		
		System.out.print(num[i]+"   ");
		}
		System.out.println();
		return num;
	}
	
	/**
	 * 将排序方法进行递归，从而得到最终结果
	 * @param num 要进行排序的数列
	 * @param start 排序那段的起始位置
	 * @param end  要排序那段的结束位置
	 * 
	 */
	
	private void Sort(int[] num, int start, int end){
		
		/**
		 * 如果开始的位置超出了结束位置，则程序可以结束，如果两者相等，则代表只排序一个元素，可以不必排序，直接返回
		 */
		
//		if(start >= end){
//			
//			return;
//			
//		}
		
		/**
		 *key得到第一轮排序好的关键值的位置，
		 *将数列分为两部分进行递归，第一部分为key左边的部分，值都比key来的小，
		 *第二部分为key右边的部分，值都比key来的大。
		 *
		 * 
		 */
		
		if(start<end){
		
		int key = Partition(num,start,end);
		Sort(num,start,key-1);
		Sort(num,key+1,end);
		
		}
		
		
		
	}
	
	/**
	 * 将数列分为两部分，左部为比关键值小的，右部为比关键值大的，这边取比关键值大的
	 * @param num 要进行排序的数列
	 * @param start 排序那段的起始位置
	 * @param end	要排序那段的结束位置
	 * @return 关键值的位置
	 */
	private int Partition(int[] num,int start,int end){
		int i = start;
		int j = end;
		int temp;
		
		
		/**
		 * 如果开始的位置小于结束的位置，则代表至少还有两个元素，要将其进入循环排序
		 */
		while(i < j){
			
			/**
			 * 从结束位置开始查找，找到第一个比关键值小的元素
			 * 
			 */
			
			while (i<j && num[i]<=num[j]) j--;
			
			/**
			 * 如果这时左边向标小于右边向标的话，则将右部比关键值小的数与关键值进行交换，将i加1，进行左部查找
			 */
			
			if(i < j){
				
				temp = num[i];
				num[i] = num[j];
				num[j] = temp;
				i++;
			}
			
			/**
			 * 从开始位置开始查找，找到第一个比关键值大的元素
			 * 
			 */
			
			while (i<j && num[i]<=num[j]) i++;
			
			/**
			 *  如果这时左边向标小于右边向标的话，则将左部比关键值大的数与关键值进行交换，将j减1，进行右部查找
			 * 
			 */
			
			if(i < j){
				
				temp = num[i];
				num[i] = num[j];
				num[j] = temp;
				j--;
			}

		
		/**
		 * 返回这时关键值的位置
		 */
		return i;
	}
	
	

}

 

   测试用例：

   QuickSortTest类：

 

package com.javaeye.rsrt;

import junit.framework.TestCase;

public class QuickSortTest extends TestCase {
	
	
	public void testSort(){
		
		QuickSort sort = new QuickSort();
		/**
		 * 测试输入值为空的情况
		 */
		int[] num = {};
		int[] values = {};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试输入值为一个的情况
		 * 
		 */
		num = new int[] {1};
		values = new int[] {1};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试输入为两个升序的情况
		 * 
		 */
		num = new int[] {1,2};
		values =new int[] {1,2};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试输入两个降序的情况
		 * 
		 */
		num = new int[]{2,1};
		values = new int[] {1,2};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试输入多个的情况
		 * 
		 */
		num = new int[] {1,66,4,7,3,42,11,44,2,87};
		values = new int[] {1,2,3,4,7,11,42,44,66,87};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试包含不规则数字情况
		 */
		num = new int[] {01};
		values = new int[] {01};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试多个包含不规则数字情况
		 */
		num = new int[] {01,1,4,04,6,07,03,2};
		values = new int[] {1,01,2,03,4,04,6,07};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试包含有一个负数的情况
		 */
		num = new int[] {-1};
		values = new int[] {-1};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		/**
		 * 测试包含有多个负数的情况
		 * 
		 */
		num = new int[] {-1,8,3,-2,77,-44,11};
		values =new int[] {-44,-2,-1,3,8,11,77};
		sort.BeginSort(num);
		for(int i =0;i<num.length;i++){
			assertEquals(num[i], values[i]);
		}
		
		
		
	}
	

}