我要记一下： 堆排序 算法时间复杂度O(nlog n) 归并排序 最好情况下还是在最坏情况下均是O(nlog2n) 快速排序 O(nlog2n)，最坏O(n ^2)
其他为 O(n ^2)
1冒泡排序
public class bubbleSort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14};// int[] data = {11,2}; sort(data); for (int i = 0; i < data.length; i++) { System.out.PRintln(data[i]); }} private static void sort(int[] data) { int temp = 0; int size = data.length; for(int i = 0;i < size - 1 ;i++){ for(int j = 0;j<size - 1 - i;j++){ if(data[j]>data[j+1]){ temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; } } } }}堆排序
public class heapsort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); } } private static void sort(int[] data) { //从最后一个节点的父节点开始// buildMaxheap(data,); for(int i = 0;i < data.length-1;i++){ buildMaxheap(data,data.length-1-i); swap(data, 0, data.length-1-i); } } private static void buildMaxheap(int[] data, int lastindex) { //从最后的一个节点判定 for(int i = (lastindex -1 )/2 ;i>=0;i--){ int k = i; while(k*2+1<=lastindex){ //左右节点对比 int biggerIndex = 2 * k +1; if(biggerIndex < lastindex){ if(data[biggerIndex]<data[biggerIndex + 1]){ biggerIndex++; } } if(data[k]<data[biggerIndex]){ //交换他们之间的位置 swap(data, k, biggerIndex); //他的子节点继续调整堆 k=biggerIndex; }else{ break; } } } } public static void swap(int[] data,int i,int j) { int temp = data[i]; data[i] = data[j]; data[j] = temp; }}插入排序
public class insertsort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14};// int[] data = {11,2}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); } } public static void sort(int[] data){ int length = data.length; int index = 0; int temp = 0; for(int i = 0;i < data.length;i++){ temp = data[i]; for(index = i;index>0&&data[index-1]>temp;index--){ data[index] = data[index-1]; } data[index] = temp; } }}归并排序
public class mergeSort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14};// int[] data = {11,2}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); }} private static void sort(int[] data) { mergesort(data,0,data.length-1); } private static void mergesort(int[] data, int low, int high) { int mid = (low + high )/2; if(low < high){ mergesort(data,low,mid); mergesort(data,mid+1,high); merge(data,low,mid,high); } } public static void merge(int[] nums,int low,int mid,int high) { //做一个数组 int[] temp = new int[high - low +1]; int i = low;//左数组 int j = mid + 1; int k = 0; while(i <= mid&& j <= high){ if(nums[i]<nums[j]){ temp[k++] = nums[i++]; }else{ temp[k++] = nums[j++]; } } while(i <=mid){ temp[k++] = nums[i++]; } // while(j <=high){ temp[k++] = nums[j++]; } for(int k2 = 0;k2 < temp.length;k2++){ nums[k2+low] = temp[k2]; } }}快速排序
public class quicksort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); } } private static void sort(int[] data) { quickSort(data,0,data.length - 1); } private static void quickSort(int[] data , int low ,int high){ if(low < high){ int middle = getMiddle(data, low, high); quickSort(data, low, middle - 1); quickSort(data, middle+1, high); } } public static int getMiddle(int[] data ,int low,int high){ //快速排序 int temp = data[low]; while(low < high){ while(low < high && data[high] > temp){ high--; } data[low] = data[high]; while(low < high&& data[high] < temp){ low++; } data[high] = data[low]; } data[low] = temp; return low; }}选择排序
public class selectSort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14};// int[] data = {11,2}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); }} private static void sort(int[] data) { int length = data.length; int temp; int index = 0; for(int i = 0 ;i < length;i++){ //标记最小的下标 temp = data[i]; index = i; for(int j = i ; j < length;j++){ //如果比较 if(data[j]<temp){ temp = data[j]; index = j; } } temp = data[index] ; data[index] = data[i]; data[i] = temp; } }}希尔排序
public class shellSort { public static void main(String[] args) { int[] data = {11,2,5,6,7,14};// int[] data = {11,2}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); }} //使用希尔排序 需要用到步长 private static void sort(int[] data) { int index; int temp ; int j;// int increment; //利用步长来判断 for(int increment = data.length/2;increment > 0;increment/=2){// temp = data[] for (int i = 0; i < data.length; i++) { //取得 temp = data[i]; //对应组来对比 for( j = i ;j >= increment;j-=increment){ if(temp < data[j - increment]){ data[j] = data[j - increment]; }else{ break; } } data[j] = temp; } } }}新闻热点
疑难解答
