Home > Java > javaTutorial > Quick sort in Java

Quick sort in Java

(*-*)浩
Release: 2019-10-22 15:53:14
forward
2998 people have browsed it

Principle of quick sort

Quick sort is an improvement on bubble sort. Bubble sort is to compare small values ​​one by one. One end, and the larger value is placed on the other end to achieve the purpose of sorting.

Quick sort in Java

Quick sorting is to first select a critical value, put the values ​​smaller than the critical value on one end, and put the values ​​larger than the critical value on the other end. . Repeat the method in the previous paragraph, and you can divide the two sides that have passed the critical value and divide them twice... After sorting the data, the entire quick sort is completed.

Quick Sort Algorithm

Core Algorithm:

//QuickSort
while(i < j) {
		while(num[j] > tmp && j > i)
			--j;
		while(num[i] <= tmp && i < j) {
			++i;
		}
		if(i < j) {
			t = num[i];
			num[i] = num[j];
			num[j] = t;
		}
	}
	num[left] = num[i];
	num[i] = tmp;
Copy after login

The following is the complete QuickSort program:

//QuickSort.java
public class QuickSort {
	public static void main(String[] args) {
		int[] num = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		System.out.print("Qriginal array is:");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
		
		//QuickSort
		quicksort(num, 0, 9);
		
		System.out.print("Sorted array is:");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
	}
	
	public static void quicksort(int[] num, int left, int right) {
		if(left > right)
			return;
		int tmp, i, j, t;
		tmp = num[left];
		i = left;
		j = right;
		while(i < j) {
			while(num[j] > tmp && j > i)
				--j;
			while(num[i] <= tmp && i < j) {
				++i;
			}
			if(i < j) {
				t = num[i];
				num[i] = num[j];
				num[j] = t;
			}
		}
		num[left] = num[i];
		num[i] = tmp;
		quicksort(num, left, i - 1);
		quicksort(num, i + 1, right);
	}
}
Copy after login

The program output is shown in the figure below:

Qriginal array is:10 9 8 7 6 5 4 3 2 1
Sorted array is:1 2 3 4 5 6 7 8 9 10
Copy after login

Quick sorting is more efficient than other sorting methods, so quick sorting is the best general sorting method now. The time complexity of QuickSort is O(nlogn).

The above is the detailed content of Quick sort in Java. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:csdn.net
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template