# java冒泡排序和快速排序

1.算法介绍

2.算法实现

```public void bubbleSort(int[] arr) {
int temp;//定义一个临时变量
for(int i=0;i<arr.length-1;i++){//冒泡趟数
for(int j=0;j<arr.length-i-1;j++){
//如果顺序不对，则交换两个元素
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}```

```public static void main(String[] args) {
Test t = new Test();
int arr[] = new int[]{13,26,22,22,35,18};
t.bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}```

[13, 18, 22, 22, 26, 35]

3.算法分析

java中Arrays.sort使用了两种排序方法，快速排序和优化的合并排序。

1.实现原理

java1.7之后的版本，开始用双轴快排取代了以前的排序算法，现在只实现了8种基本数据类型性的双轴快排，对象的排序在1.7中还在用老式的，不过都标了过时，估计以后版本中就会被新的双轴快排取代了。

2.实现代码

```/**
* Sorts the specified range of the array.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
*/
public static void sort(int[] a, int left, int right) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}

/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;

// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}

/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}

// Check special cases
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}

/*
* Create temporary array, which is used for merging.
* Implementation note: variable "right" is increased by 1.
*/
int[] b; byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);

if (odd == 0) {
b = a; a = new int[b.length];
for (int i = left - 1; ++i < right; a[i] = b[i]);
} else {
b = new int[a.length];
}

// Merging
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p] <= a[q]) {
b[i] = a[p++];
} else {
b[i] = a[q++];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i] = a[i]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
}
}```

3.源码分析

1）当待排序的数组中的元素个数较少时，源码中的阀值为7，采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)，但是当数组元素较少时，插入排序优于快速排序，因为这时快速排序的递归操作影响性能。

2）较好的选择了划分元（基准元素）。能够将数组分成大致两个相等的部分，避免出现最坏的情况。例如当数组有序的的情况下，选择第一个元素作为划分元，将使得算法的时间复杂度达到O(n^2).

当数组大小为 size=7 时 ，取数组中间元素作为划分元。int n=m>>1;(此方法值得借鉴)

当数组大小 7<size<=40时，取首、中、末三个元素中间大小的元素作为划分元。

当数组大小 size>40 时 ，从待排数组中较均匀的选择9个元素，选出一个伪中数做为划分元。

3）根据划分元 v ，形成不变式 v* (<v)* (>v)* v*

普通的快速排序算法，经过一次划分后，将划分元排到素组较中间的位置，左边的元素小于划分元，右边的元素大于划分元，而没有将与划分元相等的元素放在其附近，这一点，在Arrays.sort()中得到了较大的优化。

239 篇文章42 人订阅

0 条评论

## 相关文章

3335

3367

### 字符串的距离(动态规划) - leetcode 72

，因为在刷leetcode的动态规划专题。动态规划虽然定义很简单，但是对于复杂的动态规划题目，很多时候还是很棘手的。

862

3069

1934

1333

3504

1963

4036

### Numpy 修炼之道 （2）—— N维数组 ndarray

ndarray中的每个元素在内存中使用相同大小的块。 ndarray中的每个元素是数据类型对象的对象(称为 dtype)。

3616