# 快速排序法及优化

### 快速排序

```public class QuickSortManager {
int pivotloc;
public void quickSort(int[] arr , int low , int high){
if(low < high){
pivotloc = partition(arr, low, high);
quickSort(arr , low , pivotloc-1);
quickSort(arr, pivotloc+1, high);
}

}

int partition(int[] arr  , int low , int high){
int pivot = arr[low];
while(low < high){
while(low < high && arr[high] > pivot){
high--;
}
swap(arr, low, high);
while(low < high && arr[low] <= pivot){
low++;
}
swap(arr, low, high);
}

return low;
}

void swap(int[] arr  , int a , int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}```

```3  5  4  1  2  6 // pivot = 3
2  5  4  1  3  6
2  3  4  1  5  6
2  1  4  3  5  6
2  1  3  4  5  6  // low = 2

2 1 // pivot = 2
1 2 // low = 0

4 5 6 // pivot = 4 low = 0

### 优化

##### 简化swap

```    int partition(int[] arr  , int low , int high){
int pivot = arr[low];
while(low < high){
while(low < high && arr[high] > pivot){
high--;
calculationCount++;
}
arr[low] = arr[high];
//swap(arr, low, high);
while(low < high && arr[low] <= pivot){
low++;
calculationCount++;
}
arr[high] = arr[low];
//swap(arr, low, high);

}
arr[low] = pivot;

return low;
}```
```3  5  4  1  2  6 // pivot = 3
2  5  4  1  2  6
2  5  4  1  5  6
2  1  4  1  5  6
2  1  4  4  5  6
2  1  3  4  5  6 // low = 2

2 1 // pivot = 2
1 2 // low = 0

4 5 6 // pivot = 4 low = 0

#### 多种排序

```    void insertSort(int arr[] , int low , int high){
int i, j;
int tmp;
for (i = low + 1; i <= high; i++) {
if (arr[i] < arr[i - 1]) {

tmp = arr[i];
for (j = i - 1 ; j >= low && arr[j] > tmp ; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}
}```

```    private static final int INSERT_SORT_LENGTH = 7;
int pivotloc;
public void quickSort(int[] arr , int low , int high){
if(low < high){
if(high - low  + 1 > INSERT_SORT_LENGTH){
pivotloc = partition(arr, low, high);
quickSort(arr , low , pivotloc-1);
quickSort(arr, pivotloc+1, high);
}else{
insertSort(arr, low, high);

}

}

}```

64 篇文章27 人订阅

0 条评论

## 相关文章

421

### Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142

1843

### ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729

### 简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2189

### echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1202

992

### 高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分，其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9784

2322

### 高通msm8909耳机调试

1、DTS相应修改： DTS相关代码：kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi： 1 s...

7575