《我的第一本算法书》笔记一 (2)

伪代码：主要是递归遍历排序
public static void Sort(int[] a, int f, int e)
{
if (f < e)
{
int mid = (f + e) / 2;
Sort(a, f, mid);
Sort(a, mid + 1, e);
MergeMethid(a, f, mid, e);
}
}
private static void MergeMethid(int[] a, int f, int mid, int e)
{
int[] t = new int[e - f + 1];
int m = f, n = mid + 1, k = 0;
while(n <= e && m <= mid)
{
if (a[m] > a[n]) t[k++] = a[n++];
else t[k++] = a[m++];
}
while (n < e + 1) t[k++] = a[n++];
while (m < mid + 1) t[k++] = a[m++];
for (k = 0, m = f; m < e + 1; k++, m++) a[m] = t[k];
}

6、快速排序

快排运用了二分的思想，首先选择一个基准，定义左右两端指针，先从左到右进行扫描直到，R[hi] < temp,将R[hi]移动至lo所在位置 [公式] 从右往左进行扫描，直到R[lo] > temp,将R[lo]移动到hi所在位置上，左右端指针在排序过程中从数组的两端往中间进行靠近，直到hi == lo。而快速排序则要进行多次快排过程，直到划分的区间最后长度仅为1.
快速排序的优异之处 在于它本身会对所有的值和基准值进行比较 而这个比较 将会在整个排序周期中 只有1次 如果a<b 那么a和b将永远不会再进行比较 如果a<b<c 同样的 那么a将永远不会和c进行比较 就不会有任何的冗余操作

时间复杂度 nlogn 不稳定排序

伪代码：
void QuickSort(int R[], int lo, int hi){
int i = lo, j = hi;
int temp;
if(i < j){
temp = R[i];
while (i != j)
{
while(j > i && R[j] >= temp)-- j;
R[i] = R[j];
while(i < j && R[i] <= temp)++ i;
R[j] = R[i];
}
R[i] = temp;
QuickSort(R, lo, i - 1);
QuickSort(R, i + 1, hi);
}
}

三、数组的查找 1、线性查找 2、二分查找

通常是用于已经排好序的查找算法