The article directories

  • Bubble sort
  • – Heap sort
  • Insert sort – insert sort
  • Merge sort – merge sort
  • Quick sort – quick sort
    • Another kind of quicksort
  • Selection sort
  • Hill sorting

Bubble sort

package sort;

public class bubbleSort {

/* (1) Basic idea: in a set of numbers to be sorted, for all numbers in the range of numbers not yet sorted, * from top to bottom, compare and adjust the two adjacent numbers in turn, so that the larger number sinks down and the smaller number rises up. * That is, whenever two adjacent numbers are compared and find that their sort is the opposite of the sort required, they are swapped. * * /
	public static void main(String[] arg) {
		int a[] = {49.38.65.97.76.13.27.49.78.34.12.64.5.4.62.99.98.54.56.17.18.23.34.15.35.25.53.51};
		int temp = 0;
		for(int i = 0; i < a.length - 1; i++){
			for(int j = 0; j < a.length -1- i; j++){if( a[j] > a[j+1]){
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp; }}}for(int i = 0;i < a.length;i++){
			System.out.println(a[i]);
		}
	}
}
Copy the code

– Heap sort

package sort;

import java.util.Arrays;

/* Basic idea: heap sort is a tree selection sort, which is an effective improvement over direct selection sort. A heap is defined as follows: a sequence of n elements (H1, H2... , hn), if and only if meet > = 2 (hi > = h2i, hi I + 1) or (hi < < = h2i, hi = 2 + 1) I (I = 1, 2,... N /2) is called the heap. Only heaps that satisfy the former condition are discussed here. From the definition of the heap, the top element (that is, the first element) must be the largest item (the big top heap). A complete binary tree can represent the structure of a heap intuitively. The top of the heap is the root, and the rest are left and right subtrees. Start by thinking of the sequence of numbers to be sorted as a sequential binary tree, and adjust their storage order so that it becomes a heap, where the root node of the heap is the largest. The root node is then swapped with the last node of the heap. And then rearrange the n minus 1 number to make it a heap. And so on, until you have a heap of only two nodes, and you swap them, and you end up with an ordered sequence of n nodes. According to the algorithm description, heap sort requires two processes, one is to build the heap, and the other is to exchange the position of the top and the last element of the heap. So heapsort consists of two functions. One is the infiltration function that builds the heap, and the other is the function that calls the infiltration function repeatedly to achieve sorting. * /
public class HeapSort {

		public void heapSort(int[] a){
			System.out.println("Start sorting");
			int arrayLength = a.length;
			// Loop the heap
			for(int i = 0; i < arrayLength -1; i++){/ / build the heap
				buildMaxHeap(a,arrayLength - 1 - i);
				Swap the top and last element of the heap
				swap(a,0,arrayLength - 1 - i);
				System.out.println(Arrays.toString(a));
			}
			System.out.println("Final: " + Arrays.toString(a));
		}

		private void swap(int[] data, int i, int j) {
			int tmp = data[i];
			data[i] = data[j];
			data[j] = tmp;
		}

		// Create a large top heap from data array 0 to lastIndex
		private void buildMaxHeap(int[] data, int lastIndex) {
			// Start with the parent of the last node at lastIndex

			for(int i = (lastIndex - 1) /2; i >= 0; i--){
				//k saves the node being judged
				int k = i;
				// If the child of the current k node exists
				while(k*2 + 1 <= lastIndex){
					// Index of the left child of the k node
					int biggerIndex = 2*k + 1;
					// If biggerIndex is less than lastIndex, then the right child of the k node represented by biggerIndex+1 exists
					if(biggerIndex < lastIndex){
						// If the value of the right child node is large
						if(data[biggerIndex] < data[biggerIndex+1]) {//biggerIndex always records the index of the larger child nodebiggerIndex++; }}// If the value of k node is less than the value of its larger child node
					if(data[k] < data[biggerIndex]){
						// Swap them
						swap(data,k,biggerIndex);
						// Assign biggerIndex to k to start the next loop of the while loop, reguaranteeing that the value of k is greater than the value of its left and right children
						k = biggerIndex;
					}
					else{
						break; }}}}public static void main(String[] args) {
		int a[] ={49.38.65.97.76.13.27.49.78.34.12.64.5.4.62.99.98.54.56.17.18.23.34.15.35.25.53.51};
		HeapSort tool = newHeapSort(); tool.heapSort(a); }}Copy the code

Insert sort – insert sort

package sort;

public class insertSort {

	
	/* If (n >=2)[n>=2] is already sorted, insert the NTH number into the ordered number so that it is sorted as well. Repeat until everything is sorted. * /	
	public static void main(String[] args) {
		int a[] = {49.38.65.97.76.13.27.49.78.34.12.64.5.4.62.99.98.54.56.17.18.23.34.15.35.25.53.51};
		int temp = 0;
		for(int i = 1; i < a.length; i++){
			int j = i-1;
			temp = a[i];
			for(; j >= 0 && temp < a[j]; j--){
				a[j+1] = a[j]; // Move all values greater than temp back one unit
			}
			a[j+1] = temp;
		}

		for(int i=0;i<a.length;i++){
			System.out.println(a[i]);
		}
	}
}
Copy the code

Merge sort – merge sort

package sort;

import java.util.Arrays;

public class mergeSort {


public mergeSort(int[] a){
	sort(a,0,a.length-1);
	for(int i=0; i<a.length; i++) System.out.println(a[i]); }public void sort(int[] data, int left, int right) {

	if( left < right){
		// Find the intermediate index
		int center = (left + right)/2;
		// Recurse to the left array
		sort(data,left,center);
		// Recurse the array on the right
		sort(data,center + 1,right);
		/ / mergemerge(data,left,center,right); }}public void merge(int[] data, int left, int center, int right) {

	int [] tmpArr= new int[data.length];
	int mid = center + 1;
	//third Records the index of the intermediate array
	int third = left;
	int tmp = left;
	while(left <= center && mid <= right){
		// Put the smallest of the two arrays into the middle array
		if(data[left] <= data[mid]){
			tmpArr[third++] = data[left++];
		}
		else{ tmpArr[third++] = data[mid++]; }}// The rest is placed in the middle array
	while(mid<=right){
		tmpArr[third++] = data[mid++];
	}

	while(left<=center){
		tmpArr[third++] = data[left++];
	}

	// Copy the contents of the intermediate array back to the original array
	while(tmp<=right){
		data[tmp] = tmpArr[tmp++];
	}
	System.out.println(Arrays.toString(data));
}

	public static void main(String[] arg) {
		int a[] = {49.38.65.97.76.13.27.49.78.34.12.64.5.4.62.99.98.54.56.17.18.23.34.15.35.25.53.51};
		mergeSort tool = newmergeSort(a); tool.hashCode(); }}Copy the code

Quick sort – quick sort

package sort;

/* (1) Basic idea: Select a base element, usually choose the first or the last element, * by a trip to the scanning, will stay sequence is divided into two parts, part is smaller than base element, part of greater than or equal to base element, * base element in its correct position after the sorted, and then use the same method recursively sort divided into two parts. * * /
 
public class quickSort {

	public quickSort(int[] a){
		System.out.println("Jerry Main Entry point for quickSort: ");
		quick(a);
		for(int i = 0; i < a.length; i++){ System.out.println(a[i]); }}public int getMiddle(int[] list, int low, int high) {
		System.out.println(" Jerry I am in getMiddle, low: " + low + " high: " + high);
		int tmp = list[low]; // The first element of the array is the central axis
		while (low < high){
			while (low < high && list[high] >= tmp) {
				System.out.println("tmp: " + tmp + " list[high]: " + list[high]);
				high--;
			}

			System.out.println("Move list[high]: " + list[high] + " to list[low]: " + list[low]);
			list[low] =list[high]; // Records smaller than the central axis are moved to the low end
			while (low < high&& list[low] <= tmp) {
				low++;
			}

			System.out.println("Move list[low]: " + list[low] + " to list[high]: " + list[high]);
			list[high] =list[low]; // Records larger than the central axis are moved to the high end
		}
		System.out.println("Final !!");
		list[low] = tmp; // The central axis records to the tail
		return low; // Return the position of the center axis
	}

	public void _quickSort(int[] list, int low, int high) {
		System.out.println("Jerry I am in list: " + list + " low: " + low + " high: " + high);
		if (low < high){
			int middle =getMiddle(list, low, high); // Split the list array in two
			_quickSort(list, low, middle - 1); // Sort the low word table recursively
			_quickSort(list,middle + 1, high); // Sort the tables recursively}}public void quick(int[] a2) {
		if (a2.length > 0) { // Check if the array is empty
			_quickSort(a2,0, a2.length - 1); }}public static void main(String[] args) {
		int a[] = {3.2.4.1};
		quickSort tool = new quickSort(a);
		tool.hashCode();
		System.out.println("ok"); }}Copy the code

Another kind of quicksort

package sort;

public class QuickSort2 {

	private int[] numbers;
	private int number;
	  
	public void sort(int[] values) {
	    if (values == null || values.length == 0) {return;
	    }
	    this.numbers = values;
	    number = values.length;
	    quicksort(0, number - 1);
	  }

	  private void quicksort(int low, int high) {
	    int i = low, j = high;
	    / / pivot; A central point or center; 1. The pivot is a pivot. Slewing motion

	    int pivot = numbers[low + (high-low)/2];

	    while (i <= j) {
	      while (numbers[i] < pivot) {
	        i++;
	      }
	      while (numbers[j] > pivot) {
	        j--;
	      }

	      if(i <= j) { swap(i, j); i++; j--; }}if (low < j)
	      quicksort(low, j);
	    if (i < high)
	      quicksort(i, high);
	  }

	  private void swap(int i, int j) {
	    int temp = numbers[i];
	    numbers[i] = numbers[j];
	    numbers[j] = temp;
	  }
	  
	public static void main(String[] args) {
		int[] array = {1.3.2.4};
		QuickSort2 tool = new QuickSort2();
		tool.sort(array);
		for( int i = 0; i < array.length; i++){ System.out.println(array[i]); }}}Copy the code

Selection sort

package sort;

/* (1) Basic idea: in the set of numbers to be sorted, select the smallest number and the number of the first position swap; Then find the smallest of the remaining numbers to swap with the second position, and cycle until the penultimate number is compared to the last number. * /
public class selectSort {

	public static void main(String[] args) {
		int a[] = {1.54.6.3.78.34.12.45};
		int position = 0;
		for(int i = 0; i < a.length; i++){
			int j = i + 1;
			position = i;
			int temp = a[i];
			for(; j < a.length; j++){
				if( a[j] < temp){
					temp = a[j];
					position = j;
				}
			}
			a[position] = a[i];
			a[i] = temp;
		}

		for(int i = 0; i < a.length; i++) System.out.println(a[i]); }}Copy the code

Hill sorting

package sort;

/* Hill sort (minimum increment sort) (1) Basic idea: the algorithm is to sort the first set of numbers according to a certain increment D (n/2,n is the number of numbers to sort) into several groups, each group of records in the subscript difference D. Direct insert sort is done for all elements in each group, and then it is grouped by a smaller increment (D /2), and direct insert sort is done again in each group. When the increment is reduced to 1, the sort is complete after direct insert sort. * /
public class shilSort {

	public static void main(String[] args) {

		int a[] = {1.54.6.3.78.34.12.45.56.100};
		double d1 = a.length;
		int temp = 0;
		System.out.println("begin...");
		while(true) {
			d1 = Math.ceil( d1/2 );
			int d = (int) d1;
			for(int x = 0; x < d; x++){
				for( int i = x + d; i < a.length; i += d){
					int j = i - d;
					temp = a[i];
					for(; j >= 0 && temp < a[j]; j -= d){
						a[j+d] = a[j];
					}
					System.out.println("Jerry insert value: " + temp + 
						" to Position: < " + (j+d) + ">"); a[j+d] = temp; }}if( d == 1) {break; }}for(int i = 0; i < a.length; i++){ System.out.println(a[i]); }}}Copy the code