二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(27)

}

// 向后移动元素a[high+1..i-1]，在a[high+1]处插入a[i]

x = a[i];

for ( j=i-1; j>high; j-- )

a[j+1] = a[j];

a [high+1] = x; // 完成插入

}

}

分析

2时间复杂度O(n)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算法。

希尔排序（缩小增量排序）

思路

先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。

步骤：

01. 分成子序列(按照增量dk)；

02. 对子序列排序(直接插入排序)；

03. 缩小增量，重复以上步骤，直到增量dk=1。

增量序列中最后一个增量一定是1，如：... 9, 5, 3, 2, 1和... 13, 4, 1。如没有明确

说明增量序列可以选择... 3, 2, 1或... 5, 3, 2, 1。

例：希尔排序(52，49，80，36，14，58，61)。

dk=3

dk=2

dk=1

3/2注意：希尔排序是不稳定的。时间复杂度大约为O(n)。

程序

void ShellSort ( T a[], int n )

{

dk = n/2;

while ( dk>=1 ) {

// 一趟希尔排序，对dk个序列分别进行插入排序

for ( i=dk; i<n; i++ ) {

x = a[i];

for ( j=i-dk; j>=0 and x<a[j]; j-=dk )

a[j+dk] = a[j];

a[j+dk] = x;

}

// 缩小增量

dk = dk/2;

}

}

起泡排序

思路

26一句话，“依次比较相邻元素，‘逆序’则交换，重复n-1次”。

例：冒泡排序(52，49，80，36，14，58，61)。

52 49 80 36 14 58 61

程序

请参考错误！未找到引用源。BubbleSort算法。

分析

2比较和交换总是发生在相邻元素之间，是稳定的排序算法。时间复杂度O(n)。

快速排序

思路

一趟排序把记录分割成独立的两部分，一部分关键字均比另一部分小，然后再分别对两部分快排。

例：{52 49 80 36 14 58 61} 快速排序。

下面是一次划分的详细步骤：

26 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

整个快速排序过程如下：

(52 49 80 36 14 58 61)

程序

void QuickSort ( T a[], int low, int high ) {

if ( low < high ) {

// 划分

pivot = a[low];

i = low; j = high;

while ( i < j ) {

while ( i<j && a[j] >= pivot ) j--;a[i] = a[j];

while ( i<j && a[i] <= pivot ) i++;a[j] = a[i];

}

a[i] = pivot;

// 对子序列快排

QuickSort ( a, low, i-1); 技巧： 选第1个记录为轴，分别从后向前，从前向后扫描记录，后面“抓大放小”(如：①②)，前面“抓小放大”(如：③④)，交替进行(⑤-⑦)，最后将轴

QuickSort ( a, i+1, high);

}

}

分析

2平均情况下，时间复杂度O(nlogn)。记录本来有序时为最坏情况，时间复杂度为O(n)。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-27.html