博主主页: 码农派大星.
数据结构专栏: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. 稳定性：不稳定
