Java Sorting Algorithms - Insert Sorting, Quick Sorting, Selective Sorting, Merge Sorting, Cardinal Sorting

Straight Insertion Sort

The basic operation is to insert a record into an ordered table, which has been arranged in order, so as to get a new ordered table with the number of records increased by 1. Generally speaking, it can be operated directly on the original array.

public void insertSort(int[] nums) {
	for(int i = 1;i < nums.length;i++) {
	    int val = nums[i];
		//1. Find the location of nums[i] to insert
		int j = i-1;
		while(j >= 0 && nums[j] > val) 
			j--;
		if(j == i-1)//Explain that you don't need to move elements
			continue;
		//2. Moving Elements
		for(int t = i-1;t > j;t--)
			nums[t+1] = nums[t];
		//3. Insert Elements
		nums[j+1] = val;
	}
}

Algorithmic analysis: The basic operations of insertion sort are comparison and moving elements, and the time complexity is as followsAnd in order to stabilize the sorting, the relative position of the original ordered elements will not be changed in the sorting process.

2. Bubble Sorting

Bubble sorting is to compare the first element with the second element, exchange if it is in reverse order, and then continue to compare the second and the third, and so on. Each lie-down sequence places a maximum value in its corresponding position. For example, from ascending order, the maximum value will be put behind each order.

public void bubbleSort(int[] nums) {
	for(int i = 0;i < nums.length -1 ;i++) {
		for(int j = 0;j < nums.length -1 - i;j++) {
			if(nums[j] < nums[j+1]) {
				int temp = nums[j+1];
				nums[j+1] = nums[j];
				nums[j] = temp;
			}
		}
	}
}

Algorithmic analysis: Bubble sorting needs comparison and exchange, and the time complexity is as followsAnd it's a stable sort

Quick Sort

Through one-time sorting, the waiting records are divided into two separate parts, in which the keywords of one part of the records are smaller than the keywords of the other part of the records, and then the two parts of the records are sorted separately. Specific operations are as follows: setting two pointers low and high, setting pivot key as pivotkey, first from the high point forward search to find the first keyword less than pivotkey records and pivotkey exchange each other, and then from the low point backward search to find the first keyword greater than pivokey records and pivokey. Exchange with each other and repeat these two steps until low=high, where pivoykey is located. Quick sorting of the left and right sides, respectively

public void quickSort(int[] nums,int low,int high) {
	if(low == high || low > high)
		return;//Explain that there is only one value
	int temp1 = low;
	int temp2 = high;
	int pivotkey = nums[low];
	//Do a sort
	while(low < high) {
		while(low < high && nums[high] >= pivotkey) {//Start at high to find a number smaller than pivotkey
			high--;
		}
		nums[low] = nums[high];//Exchange with pivotkey when found
		while(low < high && nums[low] <= pivotkey) {//Start at low to find a number smaller than pivotkey
			low++;
		}
		nums[high] = nums[low];
	}
	nums[low] = pivotkey;
	//low=high when exiting the loop
	quickSort(nums,temp1,low-1);//Sinister
	quickSort(nums,low+1,temp2);//Dexter
}

Algorithmic analysis: Fast scheduling is mainly a comparison, and the time complexity is as followsAnd it's an unstable sort.

Select Sort

The basic idea of selective sorting: each record lying I n n-i-1 record selects the record with the smallest keyword as the first record of the ordered sequence.

public void selectSort(int[] nums) {
	for(int i = 0;i < nums.length-1;i++) {
		int min = nums[i];
		int index = i;
		for(int j = i+1;j < nums.length;j++) {
			if(nums[j] < min) {
				min = nums[j];
				index = j;
			}	
		}
		nums[index] = nums[i];
		nums[i] = min;	
	}
}

Algorithmic analysis: mainly for comparison, time complexity isIt's an unstable sort.

Merging Sort

Merging is to combine two or more ordered tables into a new ordered table.

//Merge Sort
public void mergeSort(int nums[]) {
	if(nums.length < 2)
		return;
	int mid = nums.length / 2;
	int[] left = new int[mid];
	int[] right = new int[nums.length - mid];
	for(int i = 0; i < mid;i++)
		left[i] = nums[i];
	for(int i = mid;i < nums.length;i++)
		right[i-mid] = nums[i];
	//Further decomposition of decomposed arrays
	mergeSort(left);
	mergeSort(right);
	//Merge when no further decomposition is possible
	merge(left,right,nums);
}
//Combine two numbers together
private void merge(int[] array1,int[] array2,int[] arrayNew) {
	//int[] arrayNew = new int[array1.length + array2.length];
	int i = 0;
	int j = 0;
	int k = 0;
	while(i < array1.length && j < array2.length) {
		if(array1[i] <= array2[j]) {
			arrayNew[k] = array1[i];
			i++;
		}else {
			arrayNew[k] = array2[j];
			j++;
		}
		k++;
	}
	//There must be an array that's over.
	for(;i < array1.length;i++) {
		arrayNew[k] = array1[i];
		k++;
	}
	for(;j < array2.length;j++) {
		arrayNew[k] = array2[j];
			k++;
	}
}

Algorithmic analysis: Time complexity isIt's a stable sort.

Heap sorting

Cardinal ordination

8. The above ranking performance comparison table

Sorting method Average time complexity Worst-case time complexity stability
Insertion sort      
Bubble sort      
Quick sort      
Selective Sorting      
Merge Sort      
Heap sorting      
Cardinal sorting      

To be continued...

Tags: less

Posted on Wed, 28 Aug 2019 00:10:29 -0700 by paul_r