数据结构各种排序算法总结
计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。
1. 冒泡排序 BubbleSort
最简单的一个
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>0; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
效率：O(N2)
2. 选择排序 selectSort
public void selectionSort()
{
int out, in, min;
for(out=0; out<nElems-1; out++) // outer loop
{
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
} // end for(out)
} // end selectionSort()
效率：O(N2)
3. 插入排序 insertSort
在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。 public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) // out is dividing line
{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
效率：比冒泡排序快一倍，比选择排序略快，但也是O(N2)
如果数据基本有序，几乎需要O(N)的时间
4. 归并排序 mergeSort
利用递归，不断的分割数组，然后归并有序数组
效率为O(N*logN),缺点是需要在存储器中有一个大小等于被排序的数据项数目的数组。 public void mergeSort() // called by main()
{ // provides workspace
long[] workSpace = new long[nElems];
recMergeSort(workSpace, 0, nElems-1);
}
//-----------------------------------------------------------
private void recMergeSort(long[] workSpace, int lowerBound,
int upperBound) {
if(lowerBound == upperBound) // if range is 1, return; // no use sorting else
{ // find midpoint int mid = (lowerBound+upperBound) / 2;
// sort low half recMergeSort(workSpace, lowerBound, mid);
// sort high half recMergeSort(workSpace, mid+1, upperBound);
// merge them merge(workSpace, lowerBound, mid+1, upperBound); } // end else
} // end recMergeSort()
//-----------------------------------------------------------
private void merge(long[] workSpace, int lowPtr,
int highPtr, int upperBound)
{
int j = 0; // workspace index int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1; // # of items while(lowPtr <= mid && highPtr <= upperBound)
if( theArray[lowPtr] < theArray[highPtr] )
workSpace[j++] = theArray[lowPtr++];
else
workSpace[j++] = theArray[highPtr++];
while(lowPtr <= mid)
workSpace[j++] = theArray[lowPtr++];
while(highPtr <= upperBound)
workSpace[j++] = theArray[highPtr++];
for(j=0; j<n; j++)
theArray[lowerBound+j] = workSpace[j];
} // end merge()
5. 希尔排序 ShellSort
public void shellSort()
{
int inner, outer;
long temp;
int h = 1; // find initial value of h while(h <= nElems/3)
h = h*3 + 1; // (1, 4, 13, 40, 121, ...) while(h>0) // decreasing h, until h=1 {
// h-sort the file for(outer=h; outer<nElems; outer++)
{
temp = theArray[outer];
inner = outer;
// one subpass (eg 0, 4, 8) while(inner > h-1 && theArray[inner-h] >= temp) {
theArray[inner] = theArray[inner-h];
inner -= h;
}
theArray[inner] = temp;
} // end for
h = (h-1) / 3; // decrease h
} // end while(h>0)
} // end shellSort()
希尔排序是基于插入排序的，由于插入排序复制的次数太多，导致效率的下降，而ShellSort先利用n-增量排序将数据变为基本有序，然后在利用插入排序（1-增量排序）。 n在排序中的一系列取值方法：Lnuth序列，间隔h=3h + 1
效率：O(N3/2) 到O(N7/6)
6. 快速排序
其根本机制在于划分：划分数据就是把数据分为两组，使所有关键字大于特定值的数据项在一组，使所有关键字小于特定值的数据项在另一组。
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left - 1; // right of first elem
int rightPtr = right + 1; // left of pivot
while(true)
{
while(leftPtr < right && // find bigger item
theArray[++leftPtr] < pivot)
; // (nop)
while(rightPtr > left && // find smaller item
theArray[--rightPtr] > pivot)
; // (nop)
if(leftPtr >= rightPtr) // if pointers cross,
break; // partition done
else // not crossed, so
swap(leftPtr, rightPtr); // swap elements
} // end while(true)
return leftPtr; // return partition
} // end partitionIt()
快速排序算法本质上通过把一个数组划分为两个子数组，然后递归的调用自身为每一个子数组进行快速排序。
枢纽（Pivot）的选择：
选择数组最右端的数据项作为枢纽：
public void recQuickSort(int left, int right)
{
if(right-left <= 0) // if size <= 1,
return; // already sorted
else // size is 2 or larger
{
long pivot = theArray[right]; // rightmost item
// partition range
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition-1); // sort left side
recQuickSort(partition+1, right); // sort right side
}
} // end recQuickSort()
//--------------------------------------------------------------
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left-1; // left (after ++)
int rightPtr = right; // right-1 (after --)
while(true)
{ // find bigger item
while( theArray[++leftPtr] < pivot )
; // (nop)
// find smaller item
while(rightPtr > 0 && theArray[--rightPtr] > pivot)
; // (nop)
if(leftPtr >= rightPtr) // if pointers cross,
break; // partition done
else // not crossed, so
swap(leftPtr, rightPtr); // swap elements
} // end while(true)
swap(leftPtr, right); // restore pivot
return leftPtr; // return pivot location
} // end partitionIt()
当数据是有序的或者是逆序时，从数组的一端或者另外一端选择数据项作为枢纽都不是好办法，比如逆序时，枢纽是最小的数据项，每一次划分都产生一个有N-1个数据项的子数组以及另外一个只包含枢纽的子数组
三数据项取中划分：
选择第一个、最后一个以及中间位置数据项的中值作为枢纽
public void recQuickSort(int left, int right)
{
int size = right-left+1;
if(size <= 3) // manual sort if small
manualSort(left, right);
else // quicksort if large
{
long median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
} // end recQuickSort()
//--------------------------------------------------------------
public long medianOf3(int left, int right)
{
int center = (left+right)/2;
// order left & center if( theArray[left] > theArray[center] )
swap(left, center);
// order left & right if( theArray[left] > theArray[right] )
swap(left, right);
// order center & right if( theArray[center] > theArray[right] )
swap(center, right);
swap(center, right-1); // put pivot on right return theArray[right-1]; // return median value } // end medianOf3()
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left; // right of first elem int rightPtr = right - 1; // left of pivot
while(true)
{
while( theArray[++leftPtr] < pivot ) // find bigger
; // (nop) while( theArray[--rightPtr] > pivot ) // find smaller
; // (nop) if(leftPtr >= rightPtr) // if pointers cross, break;
else
swap(leftPtr, rightPtr);
} // end while(true)
swap(leftPtr, right-1);
return leftPtr;
} // end partitionIt()
// partition done // not crossed, so // swap elements // restore pivot // return pivot location