This article describes the implementation method of cocktail sorting in Java exchange sorting. Share it for your reference. The details are as follows:
Cocktail sorting, that is, directional bubble sorting, cocktail stir sorting, stir sorting (can also be regarded as a deformation of selection sorting), ripples sorting, back and forth sorting or happy hour sorting, is a deformation of bubble sorting. The difference between this algorithm and bubble sorting is that when sorting, it is sorted in two directions in the sequence.
Different from bubble sorting:
Cocktail sorting is equivalent to a slight deformation of bubble sorting. The difference is from low to high and then high to low, while the bubble sort only compares each element in the sequence from low to high. He can get slightly better performance than bubble sort because bubble sort is only compared from one direction (from low to high) and only moves one item per loop.
Taking the sequence (2,3,4,5,1) as an example, cocktail sorting requires only one visit to the sequence to complete the sorting, but four times if using bubble sorting. However, in the state of a messy sequence, the efficiency of cocktail sorting and bubble sorting is very poor.
Worst time complexity O(n^2)
Optimal time complexity O(n)
Average time complexity O(n^2)
The dynamic picture of cocktail sorting is as follows:
Code analysis:
package com.baobaotao.test; /** * Sort research* */ public class Sort { /** * Classic cocktail sort* @param array The array passed in */ public static void cocatailSort(int[] array) { int length = array.length ; //Loop length/2 times for(int i=0;i<length/2;i++) { for(int j=i;j<length-i-1;j++) { if(array [j] > array[j+1]) { swap(array, j, j+1) ; } } for(int j=length-i-1;j>i;j--) { if(array[j ] < array[j-1]) { swap(array, j-1, j) ; } } printArr(array) ; } } /** * Cocktail sort (with flags) * @param array The array passed in * / public static void cocatailSortFlag(int[] array) { int length = array.length ; boolean flag1,flag2 = true ; //Loop length/2 times for(int i=0;i<length/2;i++) { flag1 = true ; flag2 = true ; for(int j=i;j<length-i-1;j++) { if(array[j] > array[j+1]) { swap(array, j, j+1 ) ; flag1 = false ; } } for(int j=length-i-1;j>i;j--) { if(array[j] < array[j-1]) { swap(array, j-1 , j) ; flag2 = false ; } } if(flag1 && flag2) { break ; } printArr(array) ; } } /** * Exchange arrays in order from small to large* @param a Array passed in * @param b The number to be exchanged incoming b * @param c The number to be exchanged incoming c */ public static void swap(int[] a, int b, int c) { int temp = 0 ; if(b < c ) { if(a[b] > a[c]) { temp = a[b] ; a[b] = a[c] ; a[c] = temp ; } } } /** * Print array* @ param array */ public static void printArr(int[] array) { for(int c : array) { System.out.print(c + " "); } System.out.println(); } public static void main( String[] args) { int[] number={11,95,45,15,78,84,51,24,12} ; int[] number2 = {11,95,45,15,78,84,51 ,24,12} ; cocatailSort(number) ; System.out.println("******************"); cocatailSortFlag(number2); } }Results analysis:
11 12 45 15 78 84 51 24 95 11 12 15 24 45 78 51 84 95 11 12 15 24 45 51 78 84 95 11 12 15 24 45 51 78 84 95 *************** *** 11 12 45 15 78 84 51 24 95 11 12 15 24 45 78 51 84 95 11 12 15 24 45 51 78 84 95
It can be seen that the number of times the cocktails is sorted is much less than that of ordinary bubble sorts. It only takes 4 times, and the improved version of the logo cocktail sorting only takes 3 times to complete the sorting.
I hope this article will be helpful to everyone's Java programming.