给艺术家做网站的工作,阜宁县建设局网站,餐饮营销策划方案,音乐展示网站建设平台目录
插入排序
直接插入排序
希尔排序
选择排序
直接选择排序
堆排序
交换排序
冒泡排序
快速排序
递归实现
优化版本
归并排序 插入排序
直接插入排序
public class MySort {public static void insertSort(int[] array) {for (int i 1; i array.length;…目录
插入排序
直接插入排序
希尔排序
选择排序
直接选择排序
堆排序
交换排序
冒泡排序
快速排序
递归实现
优化版本
归并排序 插入排序
直接插入排序
public class MySort {public static void insertSort(int[] array) {for (int i 1; i array.length; i) {int j i - 1;int tmp array[i];for (; j 0; j--) {if (tmp array[j]) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}
}
· 时间复杂度 最好情况下O(n)即数组有序的情况 最坏情况下O(n^2)即数组逆序的情况
· 空间复杂度O(1)
· 稳定性 稳定的排序算法
希尔排序
public class MySort {public static void shellSort(int[] array) {for (int gap array.length / 2; gap 1; gap / 2) {shell(array, gap);}shell(array, 1);}private static void shell(int[] array, int gap) {for (int i gap; i array.length; i) {int j i - gap;int tmp array[i];for (; j 0; j - gap) {if (tmp array[j]) {array[j gap] array[j];} else {break;}}array[j gap] tmp;}}
}
· 时间复杂度O(n^1.3)
· 空间复杂度O(1)
· 稳定性 不稳定的排序算法
选择排序
直接选择排序
public class MySort {public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIndex i;for (int j i 1; j array.length; j) {if (array[minIndex] array[j]) {minIndex j;}}swap(array, minIndex, i);}}private static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
}
· 时间复杂度O(n^2)
· 空间复杂度O(1)
· 稳定性不稳定的排序算法
堆排序
要排升序时建立大根堆排降序时建立小根堆
public class MySort {public static void heapSort(int[] array) {//1、建立大根堆 时间复杂度O(n)createHeap(array);//2、排序 时间复杂度O(n*logn)int end array.length - 1;while (end 0) {swap(array, 0, end);shiftDown(array, 0, end);end--;}}private static void createHeap(int[] array) {for (int parent (array.length-1-1) / 2; parent 0; parent--) {shiftDown(array, parent, array.length);}}private static void shiftDown(int[] array, int parent, int len) {int child 2 * parent 1;while (child len) {if (child1 len array[child] array[child1]) {child;//他一定保存的是左右孩子的最大值的下标}if (array[child] array[parent]) {swap(array, child, parent);parent child;child 2*parent 1;} else {break;}}}private static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
}
· 时间复杂度O(n*logn) 和数据是否有序无关
· 空间复杂度O(1)
· 稳定性不稳定的排序算法
交换排序
冒泡排序
public class MySort {public static void bubbleSort(int[] array) {for (int i 0; i array.length; i) {boolean flag false;for (int j 0; j array.length - i - 1; j) {if (array[j 1] array[j]) {swap(array, j 1, j);flag true;}}if (flag false) {return;}}}private static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
}
· 时间复杂度O(n^2)优化后的冒泡排序时间复杂度最好可以到O(n)
· 空间复杂度O(1)
· 稳定性稳定的排序算法
快速排序
· 时间复杂度 最好情况下O(n*logn)待排序列尽量均匀的分割 最坏情况下O(n^2)待排序列正序或逆序
· 空间复杂度 最好情况下O(logn) 最坏情况下O(n)
· 稳定性不稳定的排序算法
递归实现
public class MySort {public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start end) {return;}int pivot partition(array, start, end);quick(array, start, pivot - 1);quick(array, pivot 1, end);}private static int partition(int[] array, int left, int right) {int tmp array[left];while (left right) {while (left right array[right] tmp) {right--;}array[left] array[right];while (left right array[left] tmp) {left;}array[right] array[left];}array[left] tmp;return left;}
}
优化版本
对于快速排序的优化利用三数取中法选取key值当递归到小的区间时采用直接插入排序
public class MyQuickSort {private static final int INSERT_SIZE 100;private static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start end) {return;}if (end - start 1 INSERT_SIZE) {insertSort(array, start, end);return;}int index threeMid(array, start, end);swap(array, start, index);int pivot partition(array, start, end);quick(array, start, pivot - 1);quick(array, pivot 1, end);}/*** 针对快排的优化key值根据三数取中法获得*/private static int threeMid(int[] array, int left, int right) {int mid (left right) 1;if (array[left] array[right]) {if (array[mid] array[left]) {return left;} else if (array[mid] array[right]) {return right;} else {return mid;}} else {if (array[mid] array[right]) {return right;} else if (array[mid] array[left]) {return left;} else {return mid;}}}/*** 针对快排的优化当递归到小的区间时快排转为插入排序*/private static void insertSort(int[] array, int start, int end) {for (int i start 1; i end 1; i) {int j i - 1;int tmp array[i];for (; j start; j--) {if (tmp array[j]) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}private static int partition(int[] array, int left, int right) {int tmp array[left];while (left right) {while (left right array[right] tmp) {right--;}array[left] array[right];while (left right array[left] tmp) {left;}array[right] array[left];}array[left] tmp;return left;}private static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}
}归并排序
public class MySort {public static void mergeSort(int[] array) {mergeSortFunction(array, 0, array.length - 1);}private static void mergeSortFunction(int[] array, int low, int high) {if (low high) {return;}int mid (low high) 1;mergeSortFunction(array, low, mid);mergeSortFunction(array, mid 1, high);merge(array, low, high, mid);}private static void merge(int[] array, int low, int high, int mid) {int[] tmp new int[high - low 1];int k 0;int start1 low;int end1 mid;int start2 mid 1;int end2 high;while (start1 end1 start2 end2) {if (array[start1] array[start2]) {tmp[k] array[start1];} else {tmp[k] array[start2];}}while (start1 end1) {tmp[k] array[start1];}while (start2 end2) {tmp[k] array[start2];}for (int i 0; i k; i) {array[i low] tmp[i];}}
· 时间复杂度O(n*logn)不论有序或无序都是O(n*logn)
· 空间复杂度O(n)
· 稳定性 稳定的排序算法
