二分查找：1.必须用于有序序列
2.根据范围索引，计算中间位置索引
3.将目标值与中间值比较，确定新的搜索空间
4.持续前两步，直到找到目标位置或者超出搜索范围。
假设第k次，n/(2k)个元素内找到目标元素。
因为2k<=n，所以当且仅当n/(2k)>=1时，k最大为log2n。
时间复杂度O(h)=O(log2n).
#include<iostream>
using namespace std;
//非递归写法
int Binarysearch(int array[], int length,int key)
{
int start = 0;
int end = length - 1;
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (array[mid] == key)
{
return mid;
}
else if (array[mid] > key)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return -1;
}
//递归写法
int BinarySearchRecursion(int array[],int start,int end,int key)
{
if (start > end)
{
return -1;
}
int mid = (start + end) / 2;
if (array[mid] == key)
{
return mid;
}
else if (array[mid] > key)
{
return BinarySearchRecursion(array, start, mid - 1, key);
}
else
{
return BinarySearchRecursion(array, mid+1, end, key);
}
}
int main()
{
int array[] = { 1,2,3,4,5,6 };
cout << "非递归写法" << endl;
cout << "-------------------" << endl;
cout << "pos of 1 = " << Binarysearch(array, 6, 1) << endl;
cout << "pos of 2 = " << Binarysearch(array, 6, 2) << endl;
cout << "pos of 3 = " << Binarysearch(array, 6, 3) << endl;
cout << "pos of 4 = " << Binarysearch(array, 6, 4) << endl;
cout << "pos of 5 = " << Binarysearch(array, 6, 5) << endl;
cout << "pos of 6 = " << Binarysearch(array, 6, 6) << endl;
cout << "pos of 7 = " << Binarysearch(array, 6, 7) << endl;
cout << "-------------------" << endl;
cout << "递归写法" << endl;
cout << "-------------------" << endl;
cout << "pos of 1 = " << BinarySearchRecursion(array, 0, 6, 1) << endl;
cout << "pos of 2 = " << BinarySearchRecursion(array, 0, 6, 2) << endl;
cout << "pos of 3 = " << BinarySearchRecursion(array, 0, 6, 3) << endl;
cout << "pos of 4 = " << BinarySearchRecursion(array, 0, 6, 4) << endl;
cout << "pos of 5 = " << BinarySearchRecursion(array, 0, 6, 5) << endl;
cout << "pos of 6 = " << BinarySearchRecursion(array, 0, 6, 6) << endl;
cout << "pos of 7 = " << BinarySearchRecursion(array, 0, 6, 7) << endl;
cout << "-------------------" << endl;
system("pause");
return 0;
}插入排序：整体思想，从第二个元素开始和前面的已排序序列进行遍历比较，插入合适位置。
#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
void insertSort(int array[],int length)
{
for (int i = 1; i < length; i++)
{
for(int j = 0; j <i ; j++)
{
if (array[i] < array[j])
{
int temp = array[i];
for (int k = i-1; k >= j; k--)
{
array[k + 1] = array[k];
}
array[j] = temp;
}
}
}
}
int main()
{
int array[] = { 5,8,3,1,9,25,13};
insertSort(array, 7);
printArray(array, 7);
system("pause");
return 0;
}插入排序是稳定的，最大时间复杂度O(n2)，最小时间复杂度O(n)。
希尔排序：整体思想是缩小增量排序，设定一定大小的步长，并逐步缩小，进行不同步长下的插入排序，经过这些预排序后，序列逐渐趋于有序，最终步减为1进行插入排序。
#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
void shellSort(int array[], int length, int step)
{
for (int i = 0; i < length; i++)
{
for (int j = i + step; j < length; j += step)
{
for (int k = i; k < j; k += step)
{
if (array[j] < array[k])
{
int temp = array[j];
for (int l = j - step; l >= k; l -= step)
{
array[l + step] = array[l];
}
array[k] = temp;
}
}
}
}
}
int main()
{
int array[] = { 21,15,33,5,16,9,17,31,50,56 };
int step[3] = { 1,3,5 };
for (int i = 0; i < 3; i++)
{
shellSort(array, 10, step[i]);
}
printArray(array, 10);
system("pause");
return 0;
}存在跨越插入，希尔排序是不稳定的，最大时间复杂度为O(n2)，最小时间复杂度为O(n)。
冒泡排序：整体思想为每一趟排序相邻两元素比较大小，大的交换到右边，这样每一趟排完，待排序部分的最大值就会被冒出来，缩小待排序范围，继续进行下一趟排序。
#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
void swap(int* num1, int* num2)
{
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
void bubbleSort(int array[], int length)
{
for (int i = 0; i < length - 1; i++)
{
int flag = 1;
for (int j = 0; j < length - 1 - i;j++)
{
if (array[j + 1] < array[j])
{
flag = 0;
swap(&array[j + 1], &array[j]);
}
}
if (flag == 1)
break;
}
}
int main()
{
int array[] = { 5,8,3,1,9,25,13 };
bubbleSort(array, 7);
printArray(array, 7);
system("pause");
return 0;
}
最大时间复杂度O(n2)，最小时间复杂度也是O(n2)，优化后的最小时间复杂度是O(n)，冒泡排序是稳定的。
快速排序：主要思想是每次选待排序的序列的第一个元素作为基准，遍历序列把比基准小的放在左边，比基准大的放在右边，再对子序列重复这一过程，最终完成排序。
#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
int partition(int array[], int i, int j)
{
int temp = array[i];
while (i < j)
{
while (i<j && array[j] > temp)
{
j--;
}
if (i < j)
{
array[i] = array[j];
i++;
}
while (i < j && array[i] < temp)
{
i++;
}
if (i < j)
{
array[j] = array[i];
j--;
}
}
array[i] = temp;
return i;
}
void quickSort(int array[], int i, int j)
{
//if (i >= j)//递归出口
//{
// return;
//}
if (i < j)//两种递归出口的表达
{
int index = partition(array, i, j);
quickSort(array, i, index - 1);
quickSort(array, index + 1, j);
}
}
int main()
{
int array[] = { 5,8,3,1,9,25,13 };
quickSort(array, 0, 6);
printArray(array, 7);
system("pause");
return 0;
}#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
void quickSort(int array[], int start, int end)
{
if (start > end)
{
return;
}
int temp = array[start], left = start, right = end;
while (left < right)
{
while (left<right && array[right]>temp) right--;
array[left] = array[right];
while (left<right && array[left]<temp) left++;
array[right] = array[left];
}
array[left] = temp;
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
int main()
{
int array[] = { 5,8,3,1,9,25,13 };
quickSort(array, 0, 6);
printArray(array, 7);
system("pause");
return 0;
}
最大时间复杂度O(n2)，最小时间复杂度，每次准基都恰好能平分数组 时间复杂度O(nlogn)，快速排序不稳定（跨越式交换一般不稳定）。
221的例子
选择排序：主要思想为每一轮将max或者min下标定为第一个元素，然后遍历后面的元素不断比较来更新max或者min下标，找到最终的下标后交换首元素和max（min）。不断缩小带待排序区间，最终实现排序。
#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
void selectSort(int array[], int length)
{
for (int i = 0; i < length; i++)
{
int min = i;
for (int j = i + 1; j < length;j++)
{
if (array[j] < array[min])
{
min = j;
}
}
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
int main()
{
int array[] = { 5,8,3,1,9,25,13 };
selectSort(array, 7);
printArray(array, 7);
system("pause");
return 0;
}选择排序优化：
#include<iostream>
using namespace std;
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
}
void swap(int* num1, int* num2)
{
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
void selectSort(int array[], int length)
{
int left = 0, right = length - 1, min = left, max = right;
while (left < right)
{
for (int i = left; i <= right; i++)
{
if (array[i] < array[min])
{
min = i;
}
if (array[i] > array[max])
{
max = i;
}
}
swap(&array[max], &array[right]);
if (min == right)
{
min = max;
}
swap(array[min], array[left]);
left++;
right--;
}
}
int main()
{
int array[] = { 5,8,3,1,9,25,13 };
selectSort(array, 7);
printArray(array, 7);
system("pause");
return 0;
}选择排序最小时间复杂度为O(n2)最时间复杂度为O(n2)，但是优化后理论上可以节约一半时间。
选择排序不稳定(跨越式交换一般不稳定)。331例子。
版权声明：本文为hou19975418原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。