面试常用排序查找算法

1 二分查找

1. 定义两个变量left和right，分别表示数组的左边界和右边界，初始值分别为0和len - 1，其中len是数组的长度。
2. 计算数组的中间位置mid，公式为(left + right) / 2，并判断数组中该位置的元素num[mid]是否等于目标值target。
3. 如果相等，说明找到了目标值，返回mid作为结果。
4. 如果不相等，比较num[mid]和target的大小，如果num[mid] < target，说明目标值在数组的右半部分，因此将左边界更新为mid + 1；如果num[mid] > target，说明目标值在数组的左半部分，因此将右边界更新为mid - 1。
5. 重复步骤2到4，直到左边界大于右边界，这时说明数组中不存在目标值，返回-1作为结果。

  二分查找算法的优点是查找速度快，时间复杂度为$O(logn)$，其中n是数组的长度。缺点是要求数组必须是有序的，并且对于动态变化的数组不适用。

int BinarySearch(int num[],int target,int len)
{int left = 0, right = len - 1;while(left <= right){int mid = (left + right) / 2;if(num[mid]==target){return mid;}else if(num[mid] < target){left = mid + 1;}else{right = mid - 1;}}return -1;
}

2 冒泡排序

1. 定义一个变量i，表示数组中未排序的部分的最后一个元素的位置，初始值为length - 1，其中length是数组的长度。
2. 从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素num[j]大于后一个元素num[j+1]，则交换它们的位置，这样可以将较大的元素向后移动。
3. 重复步骤2，直到遍历到数组中未排序部分的最后一个元素，这时可以确定该元素是数组中最大的元素，并将其排在正确的位置。
4. 将变量i减一，表示数组中未排序部分的长度减少了一个元素，然后回到步骤2，继续进行比较和交换。
5. 重复步骤2到4，直到变量i小于等于1，这时说明数组中所有的元素都已经排好序，算法结束。

  冒泡排序算法的优点是简单易懂，不需要额外的空间。缺点是效率低，时间复杂度为$O(n^2)$，其中n是数组的长度。

void BubbleSort(int num[],int length)
{for(int i=length-1;i>1;i--){for(int j=0;j<i;j++){if(num[j] > num[j+1]){int tmp = num[j+1];num[j+1] = num[j];num[j] = tmp;}}}
}

3 堆排序

1. 定义一个函数MaxHeap，它的作用是将一个数组中的一部分元素调整为一个大根堆，即满足父节点的值大于等于子节点的值的二叉树。函数的参数有三个，分别是num表示数组，start表示调整的起始位置，end表示调整的结束位置。
2. 在函数MaxHeap中，定义两个变量dad和son，分别表示当前要调整的父节点和子节点的位置，初始值分别为start和start * 2 + 1（因为数组下标从0开始，所以左子节点是父节点乘以2再加1）。
3. 判断子节点是否在调整范围内，如果是，则继续执行以下步骤；如果不是，则说明已经调整完毕，返回。
4. 如果存在右子节点，并且右子节点的值大于左子节点的值，则将子节点更新为右子节点（即选择较大的子节点）。
5. 比较父节点和子节点的值，如果父节点的值大于等于子节点的值，则说明已经满足大根堆的性质，返回；如果不是，则交换父节点和子节点的值，并将父节点更新为原来的子节点，子节点更新为原来父节点的左子节点（即向下一层继续调整）。
6. 重复步骤3到5，直到调整完毕或者返回。
7. 定义一个函数HeapSort，它的作用是对一个数组进行堆排序。函数的参数有两个，分别是num表示数组，len表示数组的长度。
8. 从数组中间位置开始，依次对每个元素执行函数MaxHeap，这样可以将整个数组调整为一个大根堆（即第一个元素是最大的元素）。
9. 从数组最后一个元素开始，依次执行以下步骤：
   • 交换第一个元素和当前元素的值，这样可以将最大的元素放在正确的位置。
   • 对除了当前元素之外的其他元素执行函数MaxHeap，这样可以将剩余部分重新调整为一个大根堆（即第一个元素是剩余部分最大的元素）。
10. 重复步骤9，直到只剩下第一个元素，这时说明数组中所有的元素都已经排好序，算法结束。

  堆排序算法的优点是效率高，时间复杂度为$O(nlogn)$，其中n是数组的长度。缺点是需要额外的空间来存储堆结构，并且对于稳定性要求高的场合不适用。

void MaxHeap(int num[],int start,int end)
{int dad = start;int son = dad * 2 + 1;while(son <=end){if((son+1<=end) && (num[son]<num[son+1])){son++;}if(num[son]<num[dad]){return;}else{int tmp = num[dad];num[dad] = num[son];num[son] = tmp;dad = son;son = dad * 2 + 1;}}
}void HeapSort(int num[],int len)
{for(int i=len/2-1;i>=0;i--){MaxHeap(num,i,len-1);}for(int i=len-1;i>0;i--){int tmp = num[0];num[0] = num[i];num[i] = tmp;MaxHeap(num,0,i-1);}
}

4 插入排序

1. 定义一个变量i，表示当前要插入的元素的位置，初始值为1，表示从数组的第二个元素开始。
2. 将当前要插入的元素num[i]保存在一个临时变量tmp中，以免被覆盖。
3. 定义一个变量j，表示已经排好序的部分的最后一个元素的位置，初始值为i - 1。
4. 比较已经排好序的部分的最后一个元素num[j]和要插入的元素tmp的大小，如果前者大于后者，则将前者向后移动一位，即将num[j]赋值给num[j+1]，并将j减一；如果不是，则说明找到了要插入的位置，跳出循环。
5. 将要插入的元素tmp赋值给找到的位置，即将tmp赋值给num[j+1]。
6. 将变量i加一，表示要插入下一个元素，并回到步骤2，继续进行比较和移动。
7. 重复步骤2到6，直到变量i等于数组的长度，这时说明数组中所有的元素都已经排好序，算法结束。

  插入排序算法的优点是简单易懂，对于部分有序或者数据量较小的数组效率较高。缺点是效率低，时间复杂度为$O(n^2)$，其中n是数组的长度。

void InsertSort(int num[],int length)
{for(int i=1;i<length;i++){int tmp = num[i];int j = i - 1;while((j>=0) && (num[j]>tmp)){num[j+1] = num[j];j--;}num[j+1] = tmp;}
}

5 快速排序

1. 定义一个函数QuickSort，它的作用是对一个数组的一部分进行快速排序。函数的参数有三个，分别是num表示数组，start表示排序的起始位置，end表示排序的结束位置。
2. 判断是否需要排序，如果起始位置大于等于结束位置，则说明已经排好序，返回；如果不是，则继续执行以下步骤。
3. 定义两个变量i和j，分别表示当前要划分的部分的左边界和右边界，初始值分别为start和end。
4. 选择数组中第一个元素num[i]作为基准值，并将其保存在一个临时变量basenum中，以免被覆盖。
5. 从右边界开始，向左寻找一个小于基准值的元素，如果找到，则将其赋值给左边界位置；如果没有找到，则将右边界减一，继续寻找。
6. 从左边界开始，向右寻找一个大于基准值的元素，如果找到，则将其赋值给右边界位置；如果没有找到，则将左边界加一，继续寻找。
7. 重复步骤5和6，直到左边界和右边界相遇或者交叉，这时说明已经完成了一次划分，并将基准值赋值给相遇或者交叉的位置。
8. 对基准值左边的部分递归地执行函数QuickSort，对基准值右边的部分递归地执行函数QuickSort。
9. 重复步骤2到8，直到所有的部分都排好序，算法结束。

  快速排序算法的优点是效率高，时间复杂度为$O(nlogn)$，其中n是数组的长度。缺点是不稳定，并且对于极端情况（如数组已经有序或者逆序）效率低。

void QuickSort(int num[],int start,int end)
{if(start >= end) return;int i = start;int j = end;int basenum = num[i];while(i<j){//从右往左找小值while((i<j) && (num[j]>=basenum)){j--;}if(i<j){num[i] = num[j];i++;}//从左往右找大值while((i<j) && (num[i]<basenum)){i++;}if(i<j){num[j] = num[i];j--;}num[i] = basenum;}QuickSort(num,start,i-1);QuickSort(num,i+1,end);
}

6 选择排序

1. 定义一个变量i，表示当前要选择的位置，初始值为0，表示从数组的第一个元素开始。
2. 定义一个变量min，表示当前最小元素的位置，初始值为i。
3. 从当前位置开始，向后遍历数组中的每个元素，如果发现有比当前最小元素更小的元素，则将其位置赋值给min，这样可以找到当前范围内最小的元素。
4. 交换当前位置和最小元素的值，即将num[min]赋值给num[i]，将num[i]赋值给num[min]，这样可以将最小的元素放在正确的位置。
5. 将变量i加一，表示要选择下一个位置，并回到步骤2，继续进行选择和交换。
6. 重复步骤2到5，直到变量i等于数组的长度减一，这时说明数组中所有的元素都已经排好序，算法结束。

  选择排序算法的优点是简单易懂，不需要额外的空间。缺点是效率低，时间复杂度为$O(n^2)$，其中n是数组的长度。

void SelectSort(int num[],int length)
{for(int i=0;i<length-1;i++){int min = i;for(int j=i;j<length;j++){if(num[j]<num[min]){min = j;}}int tmp = num[min];num[min] = num[i];num[i] = tmp;}
}

7 希尔排序

1. 定义一个变量gap，表示当前要排序的元素的间隔，初始值为数组的长度length。
2. 计算新的间隔，公式为gap = gap / 3 + 1，这样可以逐渐减小间隔，直到为1。
3. 对每个间隔进行以下步骤：
   • 定义一个变量i，表示当前要排序的间隔的起始位置，初始值为0。
   • 从当前位置开始，向后遍历数组中的每个间隔内的元素，如果发现有比前一个间隔内的元素更小的元素，则将其保存在一个临时变量tmp中，并执行以下步骤：
     • 定义一个变量k，表示已经排好序的部分的最后一个间隔内的元素的位置，初始值为当前位置减去间隔，即k = j - gap。
     • 比较已经排好序的部分的最后一个间隔内的元素num[k]和要插入的元素tmp的大小，如果前者大于后者，则将前者向后移动一个间隔，即将num[k]赋值给num[k+gap]，并将k减去间隔，继续比较；如果不是，则说明找到了要插入的位置，跳出循环。
     • 将要插入的元素tmp赋值给找到的位置，即将tmp赋值给num[k+gap]。
   • 将变量i加一，表示要排序下一个间隔，并回到步骤3.2，继续进行遍历和插入。
4. 重复步骤2和3，直到变量gap等于1，这时说明数组中所有的元素都已经排好序，算法结束。

  希尔排序算法的优点是效率高于简单插入排序，时间复杂度为$O(n^{1.3})$，其中n是数组的长度。缺点是不稳定，并且对于不同的间隔选择效率有影响。

void ShellSort(int num[],int length)
{int gap = length;do{gap = gap / 3 + 1;for(int i=0;i<gap;i++){for(int j=gap+i;j<length;j+=gap){if(num[j] < num[j-gap]){int tmp = num[j];int k;for(k=j-gap;(k>=0) && (num[k]>tmp);k-=gap){num[k+gap] = num[k];}num[k+gap] = tmp;}}}} while(gap>1);
}