手写排序查找
数据与算法之美 2020-07-04
1、折半查找
思想：分治策略。把n个元素分成个数大致相同的两半，取a[n/2]与查找的key相比，一直搜索下去。
比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)
/*折半查找，非递归*/
int Binary_Search(int *a, int n, int key) //O(log n)
{
int low, mid, high;
low = 0;
high = n-1;
while(low <= high)
{
mid = (low + high) / 2;
if(a[mid] == key)
return mid;
if(a[mid] > key)
high = mid - 1;
if(a[mid] < key)
low = mid + 1;
}
return 0;
}
/*折半查找，递归实现*/
int Binary_Search2(int *a, int low, int high, int key)
{
int mid = (low + high) / 2;
if(a[mid] == key)
return mid;
if(a[mid] > key)
return Binary_Search2(a, low, mid-1, key); //有没有return都可以
else
return Binary_Search2(a, mid+1, high, key); //有没有return都可以
} 2、冒泡、选择、快速、堆
void bubblesort(int a[], int n)
{
for(int i=0; i<n-1; i++)
for(int j=0; j<n-1-i; j++)
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
}
//或者
void bubblesort(int a[], int n)
{
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
if(a[i]>a[j])
swap(a[i],a[j]);
}
————————————比较次数：1+2+......+N-1
快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
举例说明一下吧，这个可能不是太好理解。假设要排序的序列为
2 2 4 9 3 6 7 1 5 首先用2当作基准，使用i j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开。首先比较2和5，5比2大，j左移
2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置
2 1 4 9 3 6 7 1 5 比较2和4，4大于2，因此将4移动到后面
2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变
经过第一轮的快速排序，元素变为下面的样子
[1] 2 [4 9 3 6 7 5]
之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。
int quicksort(int a[], int left, int right)
{
if(left >= right){ return; }
int key = a[left];
int low = left;
int high = right;
while(low < high)
{
while(low < high && a[high] > key)
{
high--;
}
a[low] = a[high];
while(low < high && a[low] < key)
{
low++;
}
a[high] = a[low];
}
a[low] = key;
quicksort(a,left,low-1);
quicksort(a,low+1,right);
}
O(nlog2n)----O(n^2)基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
最好以及最坏都是O(nlog2n)，空间复杂度O(1).
void Create(int a[], int start, int end)
{
int temp=a[start];
for(int i=2*start+1; i<=end; i*=2) //假设根结点的序号为0（不是1），所以i结点左孩子和右孩子分别为2i+1和2i+2
{
if(i<end && a[i]<a[i+1]) //左右孩子的比较
{
++i; //i为较大的记录的下标
}
if(temp>a[i]) //左右孩子中获胜者与父亲的比较
break;
a[start] = a[i]; //将孩子结点上位，则以孩子结点的位置进行下一轮的筛选
start = i;
}
a[start]=temp;
}
void HeapSort(int a[], int n)
{
for(int i=n/2; i>=0; i--) //先建立大顶堆
{
Create(a,i,n);
}
for(int i=n-1; i>0; i--) //进行排序，最后一个元素和第一个元素进行交换
{
swap(a[i], a[0]);
Create(a,0,i-1); //将剩下的元素继续进行调整排序
}
}关于堆排序的一篇好文章：https://www.cnblogs.com/lanhaicode/p/10546257.html
========附录============
关于topK问题就不得不说了，类型有，找出前K个大的数、找出第K个大的数、找出重复K次的数
/* topK算法实现 */
#include <stdio.h>
/* 调整小顶堆，pos：唯一违反堆性质的点的位置 */
void heapsort(int *a, const int len, int pos)
{
int min;
int child = (pos * 2) + 1;// 左孩子
while (1)
{
if (child + 1 < len)// 有两个孩子
{
min = a[child] < a[child + 1] ? a[child] : a[++child];
}
else if (child + 1 == len) // 只有左孩子
{
min = a[child];
}
else
break; // 数组结束，调整完成
if (a[pos] > min)
{
a[child] = a[pos];
a[pos] = min;
pos = child; // 更新父节点索引
child = (pos * 2) + 1; // 下一个调整点
}
else
break; // 已经是堆，无需调整
}
}
/* 建立小顶堆 */
void Create(int *b, const int k)
{
int i;
for (i = k / 2 -1; i >= 0; --i)
{
heapsort(b, k, i);
}
}
/* 选出数组中最大的k个数，存入数组arr_k中 */
void top_k(const int *a,const int len, int *b, int k)
{
int i;
for (i = 0; i < k; ++i)
b[i] = a[i];
Create(b, k); // 用a的前k个数建堆
for (; i < len; ++i)
{
b[0] = a[i];
heapsort(b, k, 0);
}
}
/* 测试代码 */
int main()
{
int a[] = { 8, 1, 2, 7, 3, 4, 5, 6, 9 };
int K 4;
int i;
int b[K];
top_k(a, 9, b, K);
for (i = 0; i < K; ++i)
{
printf("%d ", b[i]);
}
return 0;
}