查找(Searching), 排序(Sorting)

查找.(Searching)

1. 顺序查找/线性查找. ( Linear Seraching ) 时间复杂度: O(N)
- 从线性表的一端开始，顺序扫描线性表，将扫描到的结点关键字和给定值k相比较. 相等，查找成功，否则失败。
- 用数组很方便.

2. 二分查找( Binary Searching ) 时间复杂度 O(log2 N) (2为下标)
- 线性表为排序表，用关键字k 域中间位置的结点的关键字比较。 循环进行下去.
- The binary search is not guaranteed to be faster for searching very mall lists.

3. 分块查找/索引顺序查找.

4. 哈希表查找. ( Hash Searching ) O(1)
- 通过对记录的关键字值进行某种运算，直接求出记录文件的地址。 addr(Ri) = H(keyi) , addr(Ri)为哈希函数.

 

排序. (Sorting)
1. 插入排序. (Insertion Sort ) 时间复杂度 [Time Complexity] : O(n2) (2为上标)
- 每一趟将一个待排序的记录，按其关键字值的大小插入到已经排序的部分文件中的适当位置上，知道全部插入完成.
void insertSort(sqlist r, int n){
int i,j;
for (i=2;i<=n;i++){
r[0]=r[i]; //r[0]是监视哨兵
j=i-1;
while(r[0].key<r[j].key){ //比K大的元素一次向后移动一格。
r[j+1]=r[j];
j--;
}
r[j+1]=r[i]; //在腾出的位置上吗插入r[i].
}
}

 

2. 希尔排序 ( Shell Sort ) 时间复杂度 O(nlog2n) . (2为下标)
- 把记录按下标的一定增量分组，对每组记录使用插入排序，随着增量的逐渐减少，所分成的组包含的记录越来越多，到增量减少为1时，整个

数据合成为一组，构成一组有序记录，完成排序。

3. 冒泡排序 （Bubble Sort ) 时间复杂度 O(n2) (2为上标 )
- 从最下面的记录开始，对每2个相邻的关键字进行比较，使进过一趟冒泡程序后，关键字最小的记录到达最上端。
void bubblesort (sqlist r, int n) {
int i, j , tmp;
for (i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--){
if(r[j].key<r[j-1].key){
tmp=r[j];
r[j]=r[j-1];
r[j-1]=tmp;
}
}

4. 快速排序. 时间复杂度 O(nlog2n) . ( 2为下标)

-快速排序是有起泡排序改进而来的
-在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放在最终位置后，数据序列被此记录分

割成两个部分。比记录小的放在前面，大的放在后面，这个过程为一趟快速排序。之后对所有的两部分分别重

复上述过程，直至每部分只有一个记录为止。
-简单的说：每趟使表的第一个元素作为支点（pivot)，将表一分为二，左小右大，对子表按递归方式继续这种

划分，直至划分的子表长为1.
-一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序的记录。
-需要设置两个指针low,high ，一个支点pivot.

5. 选择排序. (Selection Sort ) 时间复杂度 O（n2) 2为上标.
- 从 (i=1,2,3,..n-1)个记录中选择最小的记录和第i个记录交换.

6. 堆排序. (Heap Sort ) . 时间复杂度 O(nlog2n) , 2 为下标.

7. 归并排序 (Merge Sort ) 时间复杂度 O(nlog2n) , 2 为下标.

-两个有序表合成一个有序表