最近看了一些算法和数据结构的有关东西,关于数组排序还是有一点想法，所以总结一下经常用到排序
下面会根据排序的耗时分别说下：冒泡，选择，插入，希尔，快速排序
- 冒泡排序
/**
* 冒泡排序
* 比较次数：O(N*(N-1)/2)
*/
public void bubbleSort() {
System.out.println("bubbleSort");
for (int i = cIndex - 1; i > 1; i--) {
for (int j = 0; j < i; j++) {
if (theArray[j] > theArray[j + 1]) {
swap(j, j + 1);
}
}
}
}
复制代码冒泡排序算是我们学排序第一个学了，他理解起来最简单，一次次的两两对比进行调换位置，这样他的效率也是最低的。
如果是十个数比较比较次数可以推算：9+8+7+6+5+4+3+2+1=45
公式可以推出(N*(N-1)/2
他的比较次数可以看做N²/2，这边忽略了-1（当N很大的时候）
如果数据是随机，那他的交换次数可以N²/4
- 选择排序
/**
* 选择方法排序
* 比较次数：O(N*(N-1)/2)
* 交换次数比冒泡低
*/
public void selectionSort() {
System.out.println("selectionSort");
for (int i = 0; i < cIndex - 1; i++) {
for (int j = i + 1; j < cIndex; j++) {
if (theArray[i] > theArray[j]) {
swap(i, j);
}
}
}
}
复制代码当看到两层for循环嵌套他的执行效率还是N²的，但是为什么他的效率会比冒泡高呢？ 看排序的效率一般看的是比较次数和交换次数。比较次数依然一致，但是选择排序中内层循环中，每次都是把最小的放在最左边了，这样省去交换次数。
- 插入排序
/**
* 插入排序
* 比较次数：O(N*(N-1)/4)
*/
public void insertSort() {
int in, out;
System.out.println("insertSort");
for (out = 1; out < cIndex; out++) {
long temp = theArray[out];
in = out;
while (in > 0 && theArray[in - 1] > temp) {
theArray[in] = theArray[in - 1];
--in;
}
theArray[in] = temp;
}
}
复制代码重代码层面看，已经没有两层for循环，虽然也是需要两两比较但是左边已经是排序过的，如果in和in-1比较后没有进while循环体，左边的数据就不要一一比较了，随机数据的话又可以减少一半的比较
- 希尔排序
/**
* 希尔排序
* 比较次数
*/
public void shellSort() {
System.out.println("shellSort");
int in, out;
long temp;
int h = 1;
while (h < cIndex / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (out = 1; out < cIndex; out++) {
temp = theArray[out];
in = out;
while (in > h - 1 && theArray[in - h] > temp) {
theArray[in] = theArray[in - h];
in -= h;
}
theArray[in] = temp;
}
h = (h - 1) / 3;
}
}
复制代码方法已经越来越复杂了，但是效率也越来越高了。来看看希尔排序
希尔排序是基于插入排序，所以下面代码很相似。上面h = h * 3 + 1;这个是啥呢，这边的h是Knuth间隔序列。将数据分为几段进行插入排序。之后再减少h的大小，并最后到1，再执行。
排序次数我这边没有写，因为不同的N对于希尔排序的效率都不一样感觉分段都变复杂，为什么希尔排序比插入排序快很多呢？
当h值很大的时候，数据项每一趟排序需要移动的元素的个数很少，但数据项移动的距离很长。当h减小时，每一趟排序需要移动的元素个数增多，但是此时数据项已经接近于他们排序后的最终的位置，这对插入排序可以更有效率。正式两种情况的结合才是希尔排序效率那么高。
- 快速排序
效率越高的排序必定越不好理解了，所以再讲快速排序之前需要讲一下划分
/**
* 划分位置
*
* @param left
* @param right
* @param pivot
* @return
*/
public int partitionIt(int left, int right, long pivot) {
//左边指针
int leftPtr = left - 1;
//右边指针
int rightPtr = right + 1;
while (true) {
while (leftPtr < right && theArray[++leftPtr] < pivot) {
}
while (rightPtr > left && theArray[--rightPtr] > pivot) {
}
if (leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr);
}
}
return leftPtr;
}
复制代码上面就是一个划分的方法，left是数组的开始位置，right是结束位置，pivot是划分点的值，通过leftPtr右移和rightPtr左移，根据pivot的值将数据左右分开，但是并不是有序的，只能保证左边的小于pivot，右边大于pivot，左边和右边都不能保证顺序，返回值则是划分点的位置。
当这个看懂了下面才能说快速排序
/**
* 快速排序的划分
*
* @param left
* @param right
* @param pivot
* @return
*/
public int partitionItByQuickSort(int left, int right, long pivot) {
//左边指针
int leftPtr = left - 1;
//右边指针
int rightPtr = right;
while (true) {
while (theArray[++leftPtr] < pivot) {
}
while (rightPtr > 0 && theArray[--rightPtr] > pivot) {
}
if (leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr, right);
return leftPtr;
}
/**
* 快速排序
* 比较次数：O(N*logN)
*
* @param left
* @param right
*/
public void quickSort(int left, int right) {
if (right - left <= 0) {
} else {
long pivot = theArray[right];
int partition = partitionItByQuickSort(left, right, pivot);
quickSort(left, partition - 1);
quickSort(partition + 1, right);
}
}
复制代码从代码上看快速排序核心就是划分+递归。
因为是取数组本身值作为划分点，所以划分的方法有修改。然后将最右边的数据作为划分点，先将左边一层层排序，再将右边一层层排序。递归完成整个数组排序完成。它的效率是N*logN，终于出现了log了，想想二分法查找就知道为什么了。
以为有了快速排序就能为所欲为了嘛，才不是了
- 当N很大的时候因为使用了递归很有可能导致内存溢出而崩溃
- 当划分点正好是最大值或者最小值的时候，效率又回到了N²
所以这点可以采用“三数据项取中”划分，就是用数组第一个数据和最后一个数据和中间的数据，去中间值当做划分点，虽然降低了排序的效率，但是也避免了特殊情况的问题 - 当划分很小的时候可以采用插入排序，来提高排序效率