冒泡排序与快速排序

 博主主页: 码农派大星.

    数据结构专栏:Java数据结构

 数据库专栏:MySQL数据库

关注博主带你了解更多数据结构知识

1.冒泡排序

private static void swap(int[] arrary,int i,int j){int tmp = arrary[i];arrary[i] = arrary[j];arrary[j] = tmp;public static void  bubbleSort(int[] arrary){for (int i = 0; i <arrary.length-1 ; i++) {for (int j = 0; j < arrary.length-1-i; j++) {if(arrary[j]> arrary[j+1]){swap(arrary,j,j+1);}}}return arrary;}

冒泡排序总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定 

2.快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1.Hoare版

public static void  quickSort(int[] arrary){quick(arrary,0,arrary.length-1);return arrary;}private static void swap(int[] arrary,int i,int j){int tmp = arrary[i];arrary[i] = arrary[j];arrary[j] = tmp;private static void quick(int [] arrary,int start,int end){if (start >= end) {return;}int par = partition(arrary,start,end);quick(arrary,start,par-1);quick(arrary,par+1,end);}private static int partition(int [] arrary,int left,int right){int i = left;int tmp = arrary[left];while (left < right){//right-- : 先走左边会导致最后相遇的地方比基准大的数据,// 交换完后,会把大于基准的值换到前面while (left < right && arrary[right] >= tmp){right--;}while (left < right && arrary[left] <= tmp){left++;}swap(arrary,left,right);}//此时相遇left=right;swap(arrary,left,i);return right;}

2.挖坑法 

public static void  quickSort(int[] arrary){quick(arrary,0,arrary.length-1);return arrary;}
private static void quick(int [] arrary,int start,int end){if (start >= end) {return;}int par = partitionWaken(arrary,start,end);quick(arrary,start,par-1);quick(arrary,par+1,end);}
private static int partitionWaken(int [] arrary,int left,int right){int tmp = arrary[left];while (left<right){while (left < right && arrary[right] >= tmp){right--;}arrary[left] = arrary [right];while (left<right && arrary[left] <= tmp){left++;}arrary[right] = arrary[left];}arrary[left] = tmp;return left;}

3.快速排序优化

1. 三数取中法选key

public static void  quickSort(int[] arrary){quick(arrary,0,arrary.length-1);
return arrary;}private static void quick(int [] arrary,int start,int end){if (start >= end) {return;}int index = midThreeNum(arrary,start,end);swap(arrary,index,start);int par = partitionWaken(arrary,start,end);quick(arrary,start,par-1);quick(arrary,par+1,end);}private static int partitionWaken(int [] arrary,int left,int right){int tmp = arrary[left];while (left<right){while (left < right && arrary[right] >= tmp){right--;}arrary[left] = arrary [right];while (left<right && arrary[left] <= tmp){left++;}arrary[right] = arrary[left];}arrary[left] = tmp;return left;}private static int midThreeNum(int [] arrary,int left,int right){int mid = (left+right)/2;if (arrary[left] < arrary[right]){if (arrary[mid] < arrary[left]) {return left;}else if (arrary[mid] > arrary[right]){return right;}else {return mid;}}else{if (arrary[mid] < arrary[right]){return right;}else if(arrary[mid] > arrary[left]){return left;}else {return mid;}}}

2. 递归到小的子区间时，可以考虑使用插入排序

我们在数组中数据小于等于10时改为插入排序,提高了排序的效率.

 public static void  quickSort(int[] arrary){quick(arrary,0,arrary.length-1);
return arrary;}private static void quick(int [] arrary,int start,int end){if (start >= end) {return;}if (end - start + 1 <= 10) {inserSortRange(arrary,start,end);return;}int index = midThreeNum(arrary,start,end);swap(arrary,index,start);int par = partitionWaken(arrary,start,end);quick(arrary,start,par-1);quick(arrary,par+1,end);}public static  void inserSortRange(int [] array,int left,int right){for(int i = left+1; i< right;i++){int tmp = array[i];int j = i-1;for (; j >=0 ; j--) {if (array[j] > tmp) {array[j+1] = array[j];}else {//array[j+1]= tmp;break;}}array[j+1]= tmp;}}private static int partitionWaken(int [] arrary,int left,int right){int tmp = arrary[left];while (left<right){while (left < right && arrary[right] >= tmp){right--;}arrary[left] = arrary [right];while (left<right && arrary[left] <= tmp){left++;}arrary[right] = arrary[left];}arrary[left] = tmp;return left;}private static int midThreeNum(int [] arrary,int left,int right){int mid = (left+right)/2;if (arrary[left] < arrary[right]){if (arrary[mid] < arrary[left]) {return left;}else if (arrary[mid] > arrary[right]){return right;}else {return mid;}}else{if (arrary[mid] < arrary[right]){return right;}else if(arrary[mid] > arrary[left]){return left;}else {return mid;}}}

4.非递归的快速排序 

//非递归快速排序public static void quickNot(int[] array){Stack<Integer> stack = new Stack<>();int left = 0;int right = array.length - 1;int par = partition(array,left,right);if (par > left+1){stack.push(left);stack.push(par-1);}if (par < right-1){stack.push(par+1);stack.push(right);}while (!stack.isEmpty()){right = stack.pop();left = stack.pop();par = partitionWaken(array,left,right);if(par > left+1){stack.push(left);stack.push(par-1);}if (par < right -1){stack.push(par+1);stack.push(right);}}return array;}
private static int partition(int [] arrary,int left,int right){int i = left;int tmp = arrary[left];while (left < right){//right-- : 先走左边会导致最后相遇的地方比基准大的数据,// 交换完后,会把大于基准的值换到前面while (left < right && arrary[right] >= tmp){right--;}while (left < right && arrary[left] <= tmp){left++;}swap(arrary,left,right);}//此时相遇left=right;swap(arrary,left,i);return right;}

未优化的快速排序,再遇到数据过多时,程序会崩. 

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

快速排序和堆排序时间复杂度一样,但是快速排序要比堆排序快

3. 空间复杂度：O(logN)

4. 稳定性：不稳定