冒泡排序
public class 冒泡排序 {
/**
* 时间复杂度
* 最好O（n^2)
* 最坏O（n^2)
* 稳定性：稳定
* 空间复杂度O(1)
* 最好可以是O(n）但是要改进
* https://www.cnblogs.com/melon-h/archive/2012/09/20/2694941.html
* public void bubbleSort(int arr[]) {
* boolean didSwap;
* for(int i = 0, len = arr.length; i < len - 1; i++) {
* didSwap = false;
* for(int j = 0; j < len - i - 1; j++) {
* if(arr[j + 1] < arr[j]) {
* swap(arr, j, j + 1);
* didSwap = true;
* }
* }
* if(didSwap == false)
* return;
* }
* }
* @param array
*/
private static void BubbleSort(int[] array) {
if (array == null) {
return;
}
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
// int array[] = {9,8,7,6,5,4,3,2,1};
// int array[] = {1,2,3,4,5,6,7,8};
int array[] = {10, 5, 3, 1, 7, 2, 8};
System.out.println("排序之前：");
for (int element : array) {
System.out.print(element + " ");
}
BubbleSort(array);
System.out.println("\n排序之后：");
for (int element : array) {
System.out.print(element + " ");
}
}
}
堆排序
public class 堆排序 {
/**
*时间复杂度：
* 最好：O（nlog2n)
* 最坏：O（nlog2n)
* 平均：O（nlog2n）
* 稳定性：不稳定
* 稳定性的定义：https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%A8%B3%E5%AE%9A%E6%80%A7/9763250?fr=aladdin
* 空间复杂度O(1)
*/
public static void sort(int[] arr) {
/*构建大根堆*/
for (int i = (arr.length-1) / 2 - 1; i >= 0; i--) {/*执行n/2次*/
adjust(arr,i,arr.length-1);/*nlog2n*/
}
/*进行排序*/
for (int i = arr.length - 1; i > 0; i--) {/*n次*/
swap(arr, 0, i);/*把最大的放到最后，最小的放到root*/
adjust(arr, 0, i-1);/*调整大根堆*/
}
}
public static void swap(int[] arr, int start, int end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
public static void adjust(int[] arr, int i, int length) {
for (int k = i * 2 + 1; k <= length; k = k * 2 + 1) {/*log2n*/
int root = (k-1)/2;
if (k + 1 <= length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[root] < arr[k]) {
swap(arr, root, k);
} else {
break;
}
}
}
public static void main(String[] args) {
// int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int[] arr = {10, 5, 3, 1, 7, 2, 8};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
归并排序
import java.util.Arrays;
public class 归并排序 {
/**
* 时间复杂度
* 最好：O(nlog2n)
* 最坏：O(nlog2n)
* 平均：O(nlog2n)
* 稳定性：稳定
* 空间复杂度：O(n)
*/
public static void sort(int[] arr) {
int[] temp = new int[arr.length];
sort(arr, 0, arr.length - 1, temp);
}
public static void sort(int[] arr, int start, int end, int[] temp) {
if (start < end) {/*执行log2n*/
int mid = (start + end) / 2;
sort(arr, 0, mid, temp);/*左*/
sort(arr, mid + 1, end, temp);/*右*/
merge(arr, start, mid, end, temp);/*n次*/
}
}
public static void merge(int[] arr, int start, int mid, int end, int[] temp) {
int i = 0;
int s = start;
int m = mid + 1;
while (s <= mid && m <= end) {
if (arr[s] >= arr[m]) {
temp[i++] = arr[s++];
} else {
temp[i++] = arr[m++];
}
}
while (s <= mid) {/*如果m <= end 为结束条件*/
temp[i++] = arr[s++];
}
while (m <= end) {/*如果s <= mid 为结束条件*/
temp[i++] = arr[m++];
}
for (int j = 0; j < i; j++) {/*把调整后的赋给原来的数组*/
arr[start + j] = temp[j];
}
}
public static void main(String[] args) {
// int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int[] arr = {10, 5, 3, 1, 7, 2, 8};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
快速排序
public class 快速排序 {
/**
*
* 时间复杂度
* 最好：0(nlog2n)
* 最坏：O（n^2)
* 平均：O（nlog2n）
* 稳定性：不稳定
*
* 空间复杂度：O（nlog2n）
*/
public static void quickSort(int[] arr, int start, int end) {
if (start > end) {
return;
}
int left = start;
int right = end;
int temp = arr[left];
while (left <= right) {
if (left == right) {
arr[left] = temp;/*完成一个排序*/
quickSort(arr, start, left - 1);/*左边的部分*/
quickSort(arr, left + 1, end);/*右边的部分*/
break;
}
while (left < right && arr[right]>=temp) {/*找到最右边比temp小的*/
right--;
}
arr[left] = arr[right];/*不比temp小的放到左边*/
while (left < right && arr[left]<=temp) {/*找到最左边比temp大的*/
left++;
}
arr[right] = arr[left];/*把比temp大的放在右边*/
}
}
public static void main(String[] args) {
int array[] = {9,8,7,6,5,4,3,2,1};
// int array[] = {1,2,3,4,5,6,7,8};
// int array[] = {10, 5, 3, 1, 7, 2, 8};
System.out.println("排序之前：");
for (int element : array) {
System.out.print(element + " ");
}
quickSort(array, 0, array.length - 1);
System.out.println("\n排序之后：");
for (int element : array) {
System.out.print(element + " ");
}
}
}
插入排序
public class 插入排序 {
/**
* 时间复杂度
* 最坏：O（n^2)
* 平均：O(n^2)
* 最好：O（n^2)可以是O(n)需要优化：同冒泡
* 空间复杂度O(1）
* 稳定性：稳定
*/
private static void insertSort(int[] array) {
if (array == null) {
return;
}
for (int i = 1; i < array.length; i++) {/*n次*/
int temp = array[i];/*记录当前值*/
int insertIndex = i;/*记录下标*/
for (int j = i - 1; j >= 0; j--) {/*i次*/
if (temp < array[j]) {/*后移*/
array[j + 1] = array[j];
insertIndex = j;
} else {
insertIndex = j+1;
break;
}
}
array[insertIndex] = temp;/*插入*/
}
}
public static void main(String[] args) {
// int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int array[] = {1,2,3,4,5,6,7,8};
// int array[] = {10, 5, 3, 1, 7, 2, 8};
System.out.println("排序之前：");
for (int element : array) {
System.out.print(element + " ");
}
insertSort(array);
System.out.println("\n排序之后：");
for (int element : array) {
System.out.print(element + " ");
}
}
}
选择排序
public class 选择排序 {
/**
* 时间复杂度
* 最好：O(n^2)
* 最坏：O(n^2)
* 平均：O(n^2)
* 空间复杂度O(1)
* 稳定性：不稳定
*/
private static void selectSort(int[] array) {
if (array == null) {
return;
}
for (int i = 0; i < array.length; i++) {/*n次*/
int minIndex = i;/*记录当前下标*/
for (int j = i + 1; j < array.length; j++)/*找到从i开始最小的*/ /*n次*/
if (array[minIndex] > array[j])
minIndex = j;/*记录最小值的小标*/
if (minIndex != i){/*把从I开始最小的和i交换*/
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
public static void main(String[] args) {
// int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
// int array[] = {1,2,3,4,5,6,7,8};
int array[] = {10, 5, 3, 1, 7, 2, 8};
System.out.println("排序之前：");
for (int element : array) {
System.out.print(element + " ");
}
selectSort(array);
System.out.println("\n排序之后：");
for (int element : array) {
System.out.print(element + " ");
}
}
}
网友评论