JAVA中排序算法(冒泡排序、选择排序、插入排序、快速排序)

时间：2022-10-16 22:09:16

对数组｛29，75，45，17，56，45，33｝进行排序：

单项冒泡排序(每一轮选出最大数字依次排在最右)，最大时间复杂度O(n*n)

public static int[] bubbleSortByMax(int[] array) {
boolean flag = false;// 判断每一轮是否有变动,无变动说明已经是排好顺序的
for (int i = 0; i < array.length - 1; i++) {
int temp;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = true;
}
}
System.out.print("第" + i + "轮排序后:");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
if (flag) {
flag = false;
} else {
// 跳出循环
break;
}
}
return array;
}

 

双项冒泡排序(每一轮选出最大数字依次排在最右、最小的数字排在左边)，最大时间复杂度O(n) 

public static int[] towBubbleSort(int[] array) {
// 元素位置发生了交互，设置为true
boolean flag = false;

/*
 * 外层循环每次循环完毕能确定俩个数值，一个最大值一个最小值，所以循环次数减半，
 * 如果数组长度为奇数时，最后一次循环将剩余一个数值，此值必为中间值，无需再排 列；如果数组长度为偶数时，循环array.length/2
 */
int loop = array.length / 2;
for (int n = 0; n < loop; n++) {
for (int m = n; m < array.length - n - 1; m++) {
if (array[m] > array[m + 1]) {
flag = true;
// 正向冒泡
int temp = array[m];
array[m] = array[m + 1];
array[m + 1] = temp;
}
// array.length - 1 -m 倒数第1的元素，array.length - m -2倒数第2个元素
if (array[array.length - 1 - m] < array[array.length - m - 2]) {
flag = true;
// 逆向冒泡
int temp = array[array.length - 1 - m];
array[array.length - 1 - m] = array[array.length - m - 2];
array[array.length - m - 2] = temp;
}
}
System.out.print("第" + n + "轮排序后:");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
if (flag) {
// 进入下轮循环前重置为false
flag = false;
} else {
// 已为升序，跳出循环
break;
}
}
return array;
}


 

选择排序(从左边起，每一轮选出最小数和当前指针所指的数字交换位置)，最大时间复杂度O(n*n) 

public static int[] chooseSort(int[] array) {
for (int i = 0; i < array.length -1; i++) {
int temp = array[i];
int n = 0;
for (int j = i + 1; j < array.length; j++) {
if(temp > array[j]) {
n = j;
temp = array[j];
}
}
array[n] = array[i];
array[i] = temp;

System.out.print("第" + i + "轮排序后:");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
return array;
}


 

插入排序(插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置)，最大时间复杂度O(n^2) 

public static int[] insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j;
for (j = i; j > 0; j--) {
if(array[j-1] > temp) {
array[j] = array[j-1];
} else {
break;
}
}
array[j] = temp;

System.out.print("第" + i + "轮排序后:");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
return array;
}


 

快速排序(每一轮选出比当前指针所指的数字的位置，比它小的放在左边，大的放在右边)，最大时间复杂度O(nlogn) 

public static void quickSort(int[] array, int frontIndex, int lastIndex) {
if(frontIndex >= lastIndex) {
return;
}

boolean point = true;// true的时候移动last指针,false时候移动front指针

int front = frontIndex;
int last = lastIndex;
while(front != last) {
// 当书首尾指针未相遇时,比较数据
if(array[front] > array[last]) {
// 交换位置
int temp = array[front];
array[front] = array[last];
array[last] = temp;
point = !point;
}

if(point) {
// 尾指针减1
last--;
} else {
// 首指针加1
front++;
}
}

// 以指针为front时,拆分成前后两部分再次递归排序(注:此时front=last)
quickSort(array, frontIndex, --front);
quickSort(array, ++last, lastIndex);
}


 

标签：

相关文章