快速排序-Java版

系统管理员 2023-10-17 15:03 79阅读 0赞

算法特点：

某个记录为界(该记录称为支点或枢轴)，将待排序列分成两部分:  
①一部分: 所有记录的关键字大于等于支点记录的关键字  
②另一部分: 所有记录的关键字小于支点记录的关键字

算法描述：

1)任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列  
2)左侧子序列中所有记录的关键字都小于或等于基准记录的关键字  
3)右侧子序列中所有记录的关键字都大于基准记录的关键字  
4)基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。  
5)然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。

#### 基准记录也称为枢轴（或支点）记录。取序列第一个记录为枢轴记录，其关键字为Pivotkey。指针low指向序列第一个记录位置，指针high指向序列最后一个记录位置。 ####

// 划分: 把数组a[p,r]划分出左区和右区，返回值为枢轴位置j。a[p,r] ==> a[p,j-1] a[j] a[j+1,r]
    	// ---a[j]为枢轴，该元素已经排好
    	private int partition(int a[], int p, int r) {
    		int i = p;// 遍历左边的游标
    		int j = r + 1;// 遍历右边的游标
    		int x = a[p];
    		while (true) {
    			// 在左区中找一个比x大的数: a[i]
    			while (a[++i] < x && i < r);// 经过该循环,a[i]就是左区中一个比x大的数 或者 游标往右边出界了
    			// 在右区中找一个比x小的数: a[j]
    			while (a[--j] > x);// 经过该循环,a[j]就是右区中一个比x小或相等的数
    			// 如果出现i>=j,则跳循环
    			if (i >= j) {
    				break;
    			}
    			// 把a[i]和a[j]交换
    			swap(a, i, j);
    		}
    		// 把枢轴(a[p])交换到j位置，返回j
    		swap(a, p, j);
    		return j;
    	}
    
    	private void quickSort(int[] a, int p, int r) {
    		if (p < r) {// 至少两个数
    			// 思路:把组数a[p,r]划分成:a[p,q-1], a[q],a[q+1,r]
    			int q = partition(a, p, r); // 中枢位置
    			quickSort(a, p, q - 1);// 左区继续
    			quickSort(a, q + 1, r);// 右区继续
    		}
    	}
    
    	// @Test
    	public void quickSort_test() {
    		int a[] = { 21, 25, 49, 25, 16, 8, -1, 0, 23, 44 };
    		print(a);
    		quickSort(a, 0, a.length - 1);
    		print(a);
    	}

测试结果如下:

21 25 49 25 16 8 -1 0 23 44 
    -1 0 8 16 21 23 25 25 44 49

算法分析：

1)快速排序是一个递归过程，快速排序的趟数取决于递归树的高度。  
2)如果每次划分对一个记录定位后, 该记录的左侧子序列与右侧子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。

算法评价:

1)时间复杂度：

a.最好情况（每次总是选到中间值作枢轴）T(n)=O(nlogn)  
b.最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)  
2) 空间复杂度：需栈空间以实现递归  
最坏情况：S(n)=O(n)  
一般情况：S(n)=O(logn)

@@@@快速排序 优化

可以证明，快速排序算法在平均情况下的时间复杂性和最好情况下一样，也是O(nlogn)，这在基于比较的算法类中算是快速的，快速排序也因此而得名。  
快速排序算法的性能取决于划分的对称性。因此通过修改partition( )方法，可以设计出采用随机选择策略的快速排序算法，从而使期望划分更对称，更低概率出现最坏情况。

因此，可在原划分方法中加入如下代码进行优化：

public static int partition(int a[], int p, int r){
        int rand = (int)(Math.random()*(r-p));
        swap(a,p,p+rand);  //把随机选中的元素换到首元素(枢轴)
        …//原算法代码
    }