Java实现快速排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java实现快速排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.原理

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成

例: int[] test_arr[9]={3,1,2,9,7,8,6,5,4};

其"快速排序"的过程输出如下:

                     3 1 2 4 7 8 6 5 9
                     1 3 2 4 7 8 6 5 9
                     1 2 3 4 7 8 6 5 9
1 2 3 4 7 8 6 5 9
1 2 3 4 5 8 6 7 9
1 2 3 4 5 8 6 7 9
1 2 3 4 5 8 6 7 9
1 2 3 4 5 8 6 7 9
   1 2 3 4 5 6 8 7 9
1 2 3 4 5 6 7 8 9

二.源代码文章来源地址https://www.toymoban.com/news/detail-488222.html

public static  void QucikSort(long[] arr) {
		int n=arr.length;
		if(n>1){quicksort_start(arr,0,n-1);}
		else {return;}
	}
	
	private static void quicksort_start(long[] arr,int left,int right) {	
		if(left>=right)return;
		int l_pos=left;
		int r_pos=right;
		int pos=right;
		long battle=arr[pos];
		while(l_pos<r_pos)
		{
			while(arr[l_pos]<=battle&&l_pos<r_pos)
			{
				l_pos++;
			}
			while(arr[r_pos]>=battle&&l_pos<r_pos)
			{
				r_pos--;
			}
			if(l_pos<r_pos)
			{
				long tem=arr[l_pos];
				arr[l_pos]=arr[r_pos];
				arr[r_pos]=tem;
			}
			if(l_pos==r_pos)
			{
				arr[pos]=arr[l_pos];
				arr[l_pos]=battle;
			}
		}
		if(l_pos==r_pos)
		{
			quicksort_start(arr,0,l_pos-1);
			quicksort_start(arr,r_pos+1,right);
		}
	}

到了这里，关于Java实现快速排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！