面试算法之排序算法集锦
排序算法在面试过程中是经常会考的，这是很基础的，面试官觉得你应该很熟悉这些东西，如果你半个小时内写不出来，那基本就给跪了，因为这真的是狠基础狠基础的东西，所以我们得对一些基本的排序算法烂熟于胸，对这些排序思想，效率了如指掌，才能让面试官觉得你还行。基本的排序算法有：直接插入排序，冒泡排序，简单选择排序，shell排序，归并排序，快速排序，堆排序。其中归并，快速，堆排序是面试时候比较喜欢考的，因为这三个排序算法都是很重要的算法，会有很多实际的应用。下面就简单的介绍这些排序算法，并给出代码。1.直接插入排序
直接插入排序的思想很简单，就是从排序序列开始，依次将每个元素插入到前面已经排序好的序列中，最终使整个序列有序，直接插入排序的时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
*
* sorted data ; array[low...high]
*/
template <typename Type>
void DirectInsertSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
Type exchange;
int j;
for (int i = low + 1; i <= high; ++i)
{
exchange = array[i];
for (j = i - 1; j >= low; --j)
{
if (exchange < array[j])
{
array[j + 1] = array[j];
}
else
{
break;
}
}
array[j + 1] = exchange;
}
}
2.冒泡排序
我们对冒泡排序应该都比较深，因为这个名字很形象很好记 。排序的思想就是每个冒泡一遍序列，找出一个最大或最小的元素，放到它排序后的位置上直到序列有序。时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
*
* sorted data: array[low...high]
*/
template <typename Type>
void BubbleSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
Type exchange;
bool change = false;
for (int i = low; i < high; ++i)
{
for (int j = low; j < high - i + low; ++j)
{
if (array[j] > array[j + 1])
{
exchange = array[j + 1];
array[j + 1] = array[j];
array[j] = exchange;
change = true;
}
}
if (!change)
{//如果冒泡过程中没有发生交换，则视序列已经排好序，减少无谓的比较
return;
}
change = false;
}
}
3.简单选择排序
简单选择排序的思想就是每次在未排序的序列中选取一个最小（或最大）的元素，放到最终的位置上，时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
*
* sorted data ; array[low...high]
*/
template <typename Type>
void SelectSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
int index;
Type exchange;
for (int i = low; i < high; ++i)
{
index = i;
for (int j = i + 1; j <= high; ++j)
{
if (array[j] < array[index])
{
index = j;
}
}
exchange = array[i];
array[i] = array[index];
array[index] = exchange;
}
}
4.折半插入排序
折半插入排序和直接插入排序的差别就是在查找插入位置的方式上，直接插入排序是顺序查找插入位置，折半插入式通过二分搜索的思想来查找插入位置。总体来说直接插入排序的比较次数为1+2+3...+(n-1) ~ O(n^2)，二折半查找的比较次数在lg(n-1)+lg(n-2)+...1~O(lg(n!)) ~O(nlgn)（stirling公式）。所以折半查找的优势是减少了比较次数。代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
* sorted data ; array[low...high]
*/
template <typename Type>
void BinaryInsertSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
int left, right, mid, j;
Type exchange;
for (int i = low + 1; i <= high; ++i)
&nbs
补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊