Java bubble sort and bidirectional bubble sort algorithm implementation code samples
- 2020-05-09 18:35:57
- OfStack
Bubble sort:
If it is greater than/less than (depending on whether it needs to be sorted in ascending or descending order), then the substitution is performed. Otherwise, no change is made
So if I go down 1 round, I compare n minus 1 times, n is equal to the number of elements; n - 2, n - 3... One goes all the way to the last round, and we compare it one time
所以 比较次数为递减：从n-1 to 1
So the total number of comparisons is: 1+2+3+... +(n-1), is calculated by arithmetic :(1+n-1)/2*(n-1) ==
>
n/2*(n-1) ==
>
(n^2-n) * 0.5
Large O is used to represent the time complexity of the algorithm: O(n^2), ignores the coefficient 0.5 and the constant -n
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("------- Before ordering ------");
for (int j = 0; j < ary.length; j++) {
System.out.print(ary[j] + " ");
}
/*
* Ascending order. Asc1 and Asc2 Optimized the internal loop comparison times, better
* Total comparison times:
* 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);
// In descending order, you just need to take the size of the judgment replacement 1 Under the
}
static void orderAsc(int[] ary) {
int count = 0;// More times
int len = ary.length;
for (int j = 0; j < len; j++) {// The outer layer has a fixed number of cycles
for (int k = 0; k < len - 1; k++) {// Inner layer fixed cycle times
if (ary[k] > ary[k + 1]) {
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//1 Step exchange
/* Swap the values of two variables
* a=a+b
* b=a-b
* a=a-b
*/
}
count++;
}
}
System.out.println("\n-----orderAsc After sorting in ascending order ------ The number: " + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
static void orderAsc1(int[] ary) {
int count = 0;// More times
int len = ary.length;
for (int j = 0; j < len; j++) {// The outer layer has a fixed number of cycles
for (int k = len - 1; k > j; k--) {// The inner layer decreases the number of comparisons from more to less
if (ary[k] < ary[k - 1]) {
ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//1 Step exchange
}
count++;
}
}
System.out.println("\n-----orderAsc1 After sorting in ascending order ------ The number: " + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
static void orderAsc2(int[] ary) {
int count = 0;// More times
int len = ary.length;
for (int j = len - 1; j > 0; j--) {// The outer layer has a fixed number of cycles
/*
* k < j; Total number of comparisons =(n^2-n)/2
*/
for (int k = 0; k < j; k++) {// The inner layer decreases the number of comparisons from more to less
if (ary[k] > ary[k + 1]) {
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//1 Step exchange
}
count++;
}
}
System.out.println("\n-----orderAsc2 After sorting in ascending order ------ The number: " + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
}
------- Before ordering ------
898 7 862 286 879 660 433 724 316 737
-----orderAsc1 After sorting in ascending order ------ The number: 45
7 286 316 433 660 724 737 862 879 898
Bidirectional bubble sort
Bubble sort _ cocktail sort, is bidirectional bubble sort.
The difference between this algorithm and bubble sort is that the sorting is bidirectional in the sequence, and the outer layer compares the left and right boundaries l
<
r,
Inner layer 1 cycle from left to right ratio, take the high value after; 1 cycle from right to left, set the low value before;
In terms of efficiency, O(N^2) is no faster than normal bubbling
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 swaps 1 Second, and the biggest, too (n^2-n)/2 time
*/
// ary=new int[]{10,9,8,7,6,5,4,3,2,1}; // Number of test exchanges
// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; // Number of test exchanges
System.out.println("------- Before ordering ------");
for (int j = 0; j < ary.length; j++) {
System.out.print(ary[j] + " ");
}
orderAsc1(ary);
// orderAsc2(ary);
// In descending order, you just need to take the size of the judgment replacement 1 Under the
}
static void orderAsc1(int[] ary) {
int compareCount = 0;// More times
int changeCount = 0;// Switching frequency
int len = ary.length;
int left = 0, right = len -1, tl, tr;
while (left < right) {// The outer layer has a fixed number of cycles
tl = left + 1;
tr = right - 1;
for (int k = left; k < right; k++) {// The inner layer decreases the number of comparisons from more to less , From left to right
if (ary[k] > ary[k + 1]) {// The front is greater than the back, replacement
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//1 Step exchange
changeCount++;
tr = k; //1 Wheel in the last 1 When comparing, will k The index assigned to tr, tr Represents the end index value of a later comparison , From left to right, k Represents the index on the left
}
compareCount++;
}
right = tr;
for (int k = right; k > left; k--) {// The inner layer decreases the number of comparisons from more to less , From right to left
if (ary[k] < ary[k - 1]) {// After less than before replacement
ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//1 Step exchange
changeCount++;
tl = k; //1 Wheel in the last 1 When comparing, will k The index assigned to tl, tl Represents the starting index value for a later comparison , From right to left, k Represents the index on the right
}
compareCount++;
}
left = tl;
}
System.out.println("\n-----orderAsc1 After sorting in ascending order ------ Comparison times: " + compareCount + ", Number of exchanges: " + changeCount);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
// with orderAsc1 There is no difference in thinking
static void orderAsc2(int[] ary) {
int compareCount = 0;// More times
int changeCount = 0;// Switching frequency
int len = ary.length;
int l = 0, r = len -1, tl, tr;
for (; l < r; ) {// The outer layer has a fixed number of cycles
tl = l + 1;
tr = r - 1;
/*
* 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;
/*
* 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 ------ Comparison times: " + compareCount + ", Number of exchanges: " + changeCount);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
}
------- Before ordering ------
783 173 53 955 697 839 201 899 680 677
-----orderAsc1 After sorting in ascending order ------ Comparison times: 34, Number of exchanges: 22
53 173 201 677 680 697 783 839 899 955