Bubble sort:
It is to compare two adjacent elements successively according to the index. If they are greater than/less than (depending on whether they need to be sorted ascending or descending), they will be replaced. Otherwise, there will be no changes in this way. After comparing n-1 times, n is equal to the number of elements; n-2, n-3 ... until the last round, they are compared once, so the number of comparisons is decreasing: from n-1 to 1
Then the total number of comparisons is: 1+2+3+...+(n-1), calculated by arithmetic formula: (1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5
The time complexity of the algorithm is expressed by large O: O(n^2), and the coefficient 0.5 and the constant -n are ignored.
public class BubbleSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } System.out.println("-----------------"); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } /* * Ascending order, Asc1 and Asc2 optimize the number of comparisons of internal loops, which is better* Total comparisons: * Asc1, Asc2: (1+n-1)/2*(n-1) ==> n/2*(n-1) ==> n*(n-1)/2 ==>(n^2-n)/2 * Asc: n^2-n */ // orderAsc(ary); // orderAsc2(ary); orderAsc1(ary); // descending order, just need to replace the judgment size} static void orderAsc(int[] ary) { int count = 0;//number of comparisons int len = ary.length; for (int j = 0; j < len; j++) {//number of outer fixed cycles for (int k = 0; k < len - 1; k++) {//The number of inner fixed loops if (ary[k] > ary[k + 1]) { ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//One-step exchange/* Exchange two variable values* a=a+b * b=ab * a=ab */ } count++; } } System.out.println("/n------orderAsc after sorting in ascending order---------number of times: " + count); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } static void orderAsc1(int[] ary) { int count = 0;//Number of comparison int len = ary.length; for (int j = 0; j < len; j++) {//Number of fixed loops in outer layer for (int k = len - 1; k > j; k--) {//Number of comparisons in inner layer from more to less if (ary[k] < ary[k - 1]) { ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//One-step exchange} count++; } } System.out.println("/n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } static void orderAsc2(int[] ary) { int count = 0;//Number of comparisons int len = ary.length; for (int j = len - 1; j > 0; j--) {//Number of fixed cycles in outer layer/* * k < j; Total number of comparisons=(n^2-n)/2 */ for (int k = 0; k < j; k++) {//Number of comparisons decreasing from more to less in inner layer if (ary[k] > ary[k + 1]) { ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//One-step exchange} count++; } } System.out.println("/n-----orderAsc2-sorted order------number of times: " + count); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } } }-------Before sorting------ 898 7 862 286 879 660 433 724 316 737 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Two-way bubble sort
Bubble sorting_Cocktail sorting is two-way bubble sorting.
The difference between this algorithm and bubble sorting is that when sorting, it is sorted in two directions in the sequence, and the outer layer compares the left and right boundaries l<r,
A cycle in the inner layer is proportional from left to right, and the high value is set after; a cycle is based on the right to left, and the low value is set before;
In terms of efficiency, O(N^2), is no faster than ordinary bubbles
public class Bubble_CocktailSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } /* * The minimum number of exchanges is 1 time, and the maximum number is (n^2-n)/2 times*/ // ary=new int[]{10,9,8,7,6,5,4,3,2,1}; // Test the number of exchanges// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //Test exchanges System.out.println("---------------------------"); for (int j = 0; j < ary.length; j++) { System.out.print(ary[j] + " "); } orderAsc1(ary); // orderAsc2(ary); //Depending order, just need to replace the judgment size} static void orderAsc1(int[] ary) { int compareCount = 0;//Compare times int changeCount = 0;//Number of exchanges int len = ary.length; int left = 0, right = len -1, tl, tr; while (left < right) {//The number of fixed cycles of the outer layer tl = left + 1; tr = right - 1; for (int k = left; k < right; k++) {//The number of comparisons of the inner layer from more to less, from left to right if (ary[k] > ary[k + 1]) {//The front is greater than the back, substitute ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//The changeCount++ in one step; tr = k; //The index where k is located is given to tr, and tr represents the end index value of the subsequent comparison, After comparing from left to right, k represents the index on the left} compareCount++; } right = tr; for (int k = right; k > left; k--) {//The number of comparisons in the inner layer is reduced from more to less, from right to left if (ary[k] < ary[k - 1]) {//The latter is less than the pre-permutation ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//One-step exchange changeCount++; tl = k; //In the last comparison in a round, assign the index where k is located to tl, tl represents the starting index value of the subsequent comparison. After comparing from right to left, k represents the index on the right} compareCount++; } left = tl; } System.out.println("/n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- for (; l < r; ) {//The number of outer fixed cycles tl = l + 1; tr = r - 1; /* * Ratio from left to right, move the larger one to the back*/ for (int k = l; k < r; k++) { if (ary[k] > ary[k + 1]) { int temp = ary[k] + ary[k + 1]; ary[k + 1] = temp - ary[k + 1]; ary[k] = temp - ary[k + 1]; changeCount++; tr = k; } compareCount++; } r = tr; /* * Ratio from right to left, move the smaller one to the front*/ for (int k = r; k > l; k--) { if (ary[k] < ary[k - 1]) { int temp = ary[k] + ary[k - 1]; ary[k - 1] = temp - ary[k - 1]; ary[k] = temp - ary[k - 1]; changeCount++; tl = k; } compareCount++; } l = tl; } System.out.println("/n-----orderAsc2 after sorting in ascending order-------number of comparisons: " + compareCount + ", exchanges: " + changeCount); for (int j = 0; j < len; j++) { System.out.print(ary[j] + " "); } } }--------Before sorting------ 783 173 53 955 697 839 201 899 680 677 -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------