基于Visual C++2013拆解世界五百强面试题--题8-数组的排序和查找

<div class="blogpost-body" id="cnblogs_post_body">
用三种方法实现对一个数组的排序，并设计一个函数实现数的查找，要求时间越短越好，空间占用越少越好。
 
对数组排序的方法很多，我们选比较常用和容易的三种排序，直接插入排序，冒泡排序和快速排序。
直接插入排序:每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序
冒泡排序:比较相邻的元素。如果第一个比第二个大，就交换他们两个,依次让大的冒到后面 
快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 
查找的话，我们直接使用二分法查找，可以使空间占用和执行速度达到一个比较理想的效果。
 
了解了排序的基本原理，就更容易理解下面的代码了：
 

<pre class="blockcode"><code class="language-cpp">#include <stdio.h>
#include <stdlib.h>

//冒泡排序
void BubbleSort(int Nums[], int Length)
{
for (int i = 0; i < Length-1; i++)
{
 for (int j = 0; j < Length -1 - i; j++)
 {
if (Nums[j] > Nums[j + 1])//如果前一个数比后一个数大，则向后移
 //内层的一次循环完成后最大的数依次都到后面了
{
int temp = Nums[j];
Nums[j] = Nums[j + 1];
Nums[j + 1] = temp;
}
 }
}
}

//分为两个区，左边的数都比右边的数小，
//返回值为中间数所在的位置
int Partition(int Nums[], int left, int right)
{
int midNum = Nums[right];//定数组最后一个数位中间数
int j = left;
for (int i = left; i < right; i++)//循环比较第i个数和中间数
{
 if (Nums[i] < midNum)//如果小于中间数的，j指针就向后移动，
 //j指针之前的数都小于中间数
 {
if (i != j)
{
int temp = Nums[i];
Nums[i] = Nums[j];
Nums[j] = temp;
}
j++;
 }
}
//收尾工作，将中间数和j指向的中间位置的数相调换
int temp = Nums[j];
Nums[j] = midNum;
Nums[right] = temp;

return j;//返回中间数的下标
}

void QuickSort(int Nums[], int left, int right)
{
if (left < right)
{
 int mid = Partition(Nums, left, right);//分区
 QuickSort(Nums, left, mid-1);//左部分递归排序
 QuickSort(Nums, mid+1, right);//右部分递归排序
}
}

//插入排序
void InsertSort(int Nums[], int Length)
{
for (int i = 0; i < Length; i++)
{
 int j, temp = Nums[i];//将第i个数保存起来
 for (j = i - 1; Nums[j] > temp && j >= 0; j--)//依次将第i个数与前面的数比较
 {
Nums[j + 1] = Nums[j];//如果前面的书比第i个数大的，则向后移动
 }
 Nums[j + 1] = temp; //最后将空出的位置装入上面保存的第i个数
}
}

int BinarySearch(int SearchNum, int Nums[], int left, int right)
{
if (left <= right)
{
 int mid = (left + right) / 2;
 if (Nums[mid] == SearchNum)//如果中间数等于我们要查找的数字，则返回相应下标
 {
return mid;
 }
 else if (Nums[mid] < SearchNum)
 {
BinarySearch(SearchNum, Nums, mid + 1, right);//如果中间数小于我们要查找的书，则递归查询右边
 }
 else if (Nums[mid] > SearchNum)
 {
BinarySearch(SearchNum, Nums, left, mid - 1);//如果中间数大于我们要查找的书，则递归查询左边
 }
}
else//如果坐标数组下标大于右边，则说明查找不到数字，返回-1
{
 return -1;
}
}

void PrintNums(int Nums[], int Length)
{
for (int i = 0; i < Length; i++)
{
 printf("%3d", Nums[i]);
}
printf("\n");
}

int main()
{
int Nums[10] = { 21, 4, 44, 13, 8, 1, 5, 6, 7, 14 };
//BubbleSort(Nums, 10);
//InsertSort(Nums, 10);
//使用那个快速排序
QuickSort(Nums, 0, 9);
//打印出排序后的结果
PrintNums(Nums, 10);

//使用二分法查找数字
int SearchNum = 21;
int SearchNumIndex = BinarySearch(SearchNum, Nums, 0, 9);
printf("查找到%d数字下标:%d \n", SearchNum, SearchNumIndex);

return 0;
}</code></pre>
 
 

运行结果：
<img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAmIAAAD6CAYAAAAC/CvhAAAgAElEQVR4Aey9C3xdxXUuvuQXaWxwbJAs2dCmOMGAQm9kjHMhJJjw6pVDW9MK8qoDiGKwlQfk6dgEkdgxeZKHzCtxAuQmDSENv8ag2/J0kgZax1i3/8S8UpPeXyxLloIdGzsJxrb+61sza+/Z++xzdI50JB1Ja6Rz9jzWrFnzzey9vzMze3bVaae9sW/mzBrav/9FGqzr7e0VFa9cMp0O8Sd0k364lybzJ59bt24drVy5Mie5pqYmJ65QRE9PT6FkSzMEDAFDwBAwBAwBQ6BiEJhQMZaYIYaAIWAIGAKGgCFgCIwzBIyIjbMGt+oaAoaAIWAIGAKGQOUgYESsctrCLDEEDAFDwBAwBAyBcYaAEbFx1uBWXUPAEDAEDAFDwBCoHAQmVY4p5bFk6tSp5VFkWgyBEUTgwIEDI1i6FW0IGAKGgCEw