数据结构各种排序算法总结

计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。

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