文章目录
参考了 这篇博客
总体总结表：这个有个错误就是归并排序需要一个o(n)的辅助数组
#冒泡排序
主要思想：外层循环从1到n-1，内循环从当前外层的元素的下一个位置开始，依次和外层的元素比较，出现逆序就交换。
特点： sort（稳定性排序）、In-place sort（不占用额外的空间,只是交换元素）
最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。
最差复杂度：当输入数组为倒序时java堆排序算法，复杂度为O(n^2)
插入排序比较适合用于“少量元素的数组”。
其实插入排序的复杂度和逆序对的个数一样，当数组倒序时，逆序对的个数为n(n-1)/2，因此插入排序复杂度为O(n^2)。
public class BubbleSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 4, 5, 1, 6, 8, 7};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
int n = array.length;
for(int i = 0; i < arr.length - 1; i++){
for(int j = 0; j < arr.length - 1 - i; j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
在算法导论思考题2-2中又问了”冒泡排序和插入排序哪个更快“呢？
插入排序的速度直接是逆序对的个数，而冒泡排序中执行“交换“的次数是逆序对的个数，因此冒泡排序执行的时间至少是逆序对的个数，因此插入排序的执行时间至少比冒泡排序快。
#插入排序
主要思想：
特点： sort(稳定性排序)、In-place sort（不占用额外空间）
最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。
最差复杂度：当输入数组为倒序时，复杂度为O(n^2)
插入排序比较适合用于“少量元素的数组”。
其实插入排序的复杂度和逆序对的个数一样，当数组倒序时，逆序对的个数为n(n-1)/2，因此插入排序复杂度为O(n^2)。
public class InsertSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 4, 5, 1, 6, 8, 7};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
int n = array.length;
for (int i = 1; i < n; i++) {
for (int j = i ; j >0 ; j--) {
if (array[j] < array[j - 1]) {
int temp = array[j];
array[j] = array[j - 1];
array[j-1] = temp;
}
}
}
}
}
插入排序的改进：内循环发现逆序不交换，采用整体右移，直到没有逆序的时候把元素放在该位置
public class InsertSort2 {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
int n = array.length;
for (int i = 1; i < n; i++) {
int key = array[i];
int j = i -1;
while (j >= 0 && array[j]>key) {
array[j + 1] = array[j];
j--;
}
array[j+1] = key;
}
}
}
问题：快速排序（不使用随机化）是否一定比插入排序快？
答：不一定，当输入数组已经排好序时java堆排序算法 十大排序算法 JAVA代码，插入排序需要O(n)时间，而快速排序需要O(n^2)时间。
#选择排序
特性：In-place sort， sort。
思想：每次找一个最小值。
最好情况时间：O(n^2)。
最坏情况时间：O(n^2)。
public class SelectSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
int n = array.length;
for (int i = 0; i < n-1; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (array[j] < array[min]) min = j;
}
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
#希尔排序
思想：基于插入排序，交换不相邻的元素已对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。思想是使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组.
特性：In-place sort， sort。
思想：每次找一个最小值。
最好情况时间：O(n)。
最坏情况时间：O(n^2)。
public class ShellSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7, 15};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
int n = array.length;
int h = 1;
while (h= 1) {
for (int i = h; i < n; i++) {
for (int j = i; j >= h && (array[j] < array[j - h]); j -= h) {
int temp = array[j];
array[j] = array[j - h];
array[j-h]= temp;
}
}
h /=3;
}
}
}
#归并排序
特点： sort、Out-place sort
思想：运用分治法思想解决排序问题。
最坏情况运行时间：O(nlgn)
最佳运行时间：O(nlgn)
程序中merge的精髓（也就是排序）：左半边用尽，则取右半边元素；右半边用尽，则取左半边元素；右半边的当前元素小于左半边的当前元素，则取右半边元素；右半边的当前元素大于左半边的当前元素，则取左半边的元素。实际上大部分发生的都是后面两句话，前面两句只是特殊情况而已。
自顶向下：
<pre>public class MergeSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7};
mergeSort(array);
System.out.println(Arrays.toString(array));
}
private static void mergeSort(int[] array) {
int[] aux = new int[array.length];
sort(array, aux, 0, array.length - 1);
}
private static void sort(int[] array, int[] aux, int lo, int hi) {
if (hi hi) array[k] = aux[i++];<p>
else if (aux[j]