快速排序
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。
java版本实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
private static int partition(int[] arr, int begin, int end) {
int pivot = arr[begin];
while (begin < end) {
while (begin < end && arr[--end] >= pivot) ;
arr[begin] = arr[end];
while (begin < end && arr[++begin] <= pivot) ;
arr[end] = arr[begin];
}
arr[begin] = pivot;
return begin;
}
private static void quickSort(int[] arr, int begin, int end) {
if (begin >= end) return;
int middle = partition(arr, begin, end);
quickSort(arr, begin, middle - 1);
quickSort(arr, middle + 1, end);
}
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length);
}
|
插入排序
排序思想相对简单，类似打扑克那排，拿到一张就按大小将其插入适当的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
|
折半插入排序
因为前面是已经排好序的，后面一个在寻找插入点时，可以进行折半查找。
描述：
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素大，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static void binaryInsertSort(int[] arr){
for(int i = 1;i < arr.length;i++){
int temp = arr[i];
int right = i - 1;
int left = 1;
while(left <= right){
int mid = (right + left) / 2;
if(arr[mid] > temp )
right = mid - 1;
else left = mid + 1;
}
for(int j = i -1;j > right;j--){
arr[j + 1] = arr[j];
}
arr[right + 1] = temp;
}
}
|
希尔排序
希尔排序，也称为递减增量排序算法,是插入排序的一种高效的改进版本。
希尔排序是一种稳定的排序算法，时间复杂度为O(n^3/2);
希尔算法是基于插入排序的一下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好的数据操作时，效率高，即可达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
算法描述：
- 先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序
- 然后取 d2(d2 < d1)
- 重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void shellSort(int[] arr, int n){
int i,j ,gap;
for(gap = n/2; gap > 0; gap /= 2){
for(i = 0; i < gap; i++){
for(j = i + gap;j < arr.length; j += gap){
int temp = arr[j];
int k = j - gap;
while(k >= i && arr[k] > temp){
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = temp;
}
}
}
}
|
参考：几种基本的插入排序
