The sorting

Bubble sort

Bubble sort is a typical commutative sort.

Swap sort, as the name implies, is to judge whether the elements meet the requirements by comparing them in pairs. If the elements do not meet the requirements, swap positions to achieve the purpose of sorting. Bubbling sort gets its name from the fact that during the exchange process, small (or large) elements slowly rise from the bottom to the top of the water, similar to bubbling.

The idea of bubble sort is to use the comparison exchange, using a loop to return the ith smallest or largest element. The return operation uses the comparison of the two adjacent elements in n, if the order is correct, no exchange, if the order is wrong, the position of the exchange. By iterating through the array until there are no more elements to swap, the sorting is complete

Resolution:

  1. The outermost layer describes the number of trips

  2. The inner layer compares pairwise values

    public static void sortData(int[] array){ if(array == null || array.length == 0){ return; } int temp; for(int i=0; i<array.length -1; i++){ for(int j=0; j<array.length-1-i; j++){ if(array[j+1] > array[j]){ temp = array[j+1]; array[j+1] = array[j]; array[j]=temp; } } } for(int k:array){ System.out.println(k); }}Copy the code

Quick sort

Quicksort is a sorting algorithm developed by Tony Hall. On average, order n two items and compare them (nlogn) several times. In the worst case, a comparison of TWO (N2) steps is required, but this is not common. In fact, quicksort is generally significantly faster than any other two (NLOGN) algorithms because its inner loop can be implemented efficiently on most architectures.

Quicksort uses a Divide and conquer strategy to Divide one serial (list) into two sub-lists. Quicksort is a typical application of divide-and-conquer in sorting algorithm. Quicksort is essentially a recursive divide-and-conquer method based on bubble sort.

Quicksort’s name is simple and rude, because when you hear the name you know it is fast, and efficient! It’s one of the fastest sorting algorithms for big data. Although Worst Case has O(n²) time complexity, it is excellent and performs better in most cases than sorting algorithms with O(n logn) average time complexity.

public static int[] quickSort(int[] arr,int left,int right){ if(left < right){ int partition = partition(arr,left,right); partition(arr,left,partition -1); partition(arr,partition+1,right); } } public static int partition(int[] array,int left,int right){ int pivot = left; int index = pivot + 1; for(int i=index; i<=right; i++){ if(array[i] < array[pivot]){ swap(array,i,index); index++; } } swap(array,pivot,index -1); return index -1; } private static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }Copy the code

Heap sort

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. Heap sort can be said to be a selection sort that uses the concept of heap to sort. There are two methods:

Large top heap: Each node has a value greater than or equal to the value of its children, used in ascending heap sorting;

Small top heap: The value of each node is less than or equal to the value of its children, used in descending order in the heap sort algorithm;

The average time complexity of heap sort is two o (nlogn).

\1. Algorithm steps

Create a heap H[0…… n-1];

Swap the heap head (maximum) with the heap tail;

Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.

Repeat step 2 until the heap size is 1.

private static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private void heapify(int[] arr, int i,int len){ int left = 2*i +1; int right = 2*i+ 2; int largest = i; if(left <len && arr[left] > arr[largest]){ largest = left; } if(right < len && arr[right] > arr[largest]){ largest = right; } if(largest ! = i){ swap(arr,i,largest ); heapify(arr,largest,len); } } private void buildMaxHeap(int[] arr,int len){ for(int i=(int)Math.floor(len/2); i>=0; i--){ heapify(arr,i,len); } } public int[] heapSort(int[] sorce){ int[] arr = Arrays.copyOf(sorce,sorce.length); int len = arr.length; buildMaxHeap(arr,len); for(int i = len -1; i>0; i--){ swap(arr,0,i); len--; heapify(arr,0,len); } return arr; }Copy the code