目录
一、冒泡排序
二、选择排序
三、插入排序
四、希尔排序
五、堆排序
六、快速排序
6.1 key位置选择
6.2 一趟排序的方法
hoare版本
挖坑法
前后指针法
6.3 完整排序
七、归并排序
一、冒泡排序
通过两两顺序比较,把大的值往后挪动。
一趟:将当前位置的值与下一个比较,如果当前值大于下一个位置的值则交换(升序),一趟可以做到把最大值放在最后位置。
n个数n-1躺:第一趟比较n-1次,第二趟就只要比较n-2次,最后第n-1躺只剩一个数就不需要再比较,到此排序完成。
时间复杂度:O(n2)
可以设置一个标志位,如果某一趟排序没有发生交换,那么说明已经有序,后续就不需要操作了。
// 冒泡排序
void BubbleSort(vector<int>& a)
{
int n = a.size();
for (int i = 0; i < n - 1; i++)
{
bool flag = true;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
flag = false;
}
}
if (flag)
break;
}
}
二、选择排序
也是一种比较暴力的排序。
一趟:图中是遍历一次选择最小值放前面,代码中稍微优化了一下,一次把最大值和最小值都跳出来,但是本质上时间复杂度没有提高
n个数n-1躺:一趟后最大值和最小值选出来,那么就可以左右两边缩小一个位置再遍历找除最大值和最小值,一直到最中间的两个位置,排序完成。
时间复杂度:O(n2)
void SelectSort(vector<int>& a)
{
int n = a.size();
int beg = 0, end = n - 1;
while (beg < end)
{
int maxi = beg, mini = end;
for (int i = beg; i <= end; i++)
{
if (a[i] > a[maxi]) maxi = i;
if (a[i] < a[mini]) mini = i;
}
swap(a[beg++], a[mini]);
//这里有一个坑,如果min跟end位置相同,
//max和end中的值交换后,此时min中的值被改变
if (mini == end)
mini = maxi;
swap(a[end--], a[maxi]);
}
}
三、插入排序
插入排序类似打扑克排时码牌的过程。
一趟:将要插入的值从后往前比较,如果插入值小于前一个值(升序),将前一个值往后挪,再接着往前比较,如果找到大于前一个位置那么就插入到该位置。
n个数n-1躺:第一趟就一个数不用比较,后面需要比较数的增加。到第n个数最坏要比较n-1次。
时间复杂度:O(n2)
近似有序的情况下,插入排序就很块。
void InsertSort(vector<int>& a)
{
int n = a.size();
for (int i = 0; i < n - 1; i++)
{
int end = i;
int insertV = a[end + 1];
while (end >= 0)
{
if (insertV < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = insertV;
}
}
四、希尔排序
希尔排序是插入排序的优化,前面说到插入排序在近似有序时效果比较好。那么我们可以先预排序,具体的做法就是将一组数,分组进行插入排序。设定一个间距gap,比如gap是2时就会跳一个数是一组。慢慢地减小gap,直到gap=1就是插入排序,到此希尔排序完成。
时间复杂度:比较复杂难以计算,可以认为是O(n1.3)
void ShellSort(vector<int>& a)
{
int n = a.size();
int gap = n;
while (gap > 1)
{
gap /= 2;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int insertV = a[end + gap];
while (end >= 0)
{
if (insertV < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = insertV;
}
}
}
五、堆排序
利用堆地特性,排升序用大堆,降序用小堆。先将数组建成堆,把堆顶元素放到数组最后,再重新建堆,继续把堆顶地值往最后调,直到只剩堆顶则排序完成。
时间复杂度:O(nlogn)
void AdjustDwon(vector<int>& a, int n, int root)
{
int child = root * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
child++;
if (a[child] > a[root])
{
swap(a[child], a[root]);
root = child;
child = root * 2 + 1;
}
else
break;
}
}
void HeapSort(vector<int>& a)
{
int n = a.size();
// 建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
AdjustDwon(a, n, i);
for (int i = n - 1; i > 0; i--)
{
// 将最大值放到数组最后
swap(a[0], a[i]);
// 将交换后的对顶元素下沉,保持堆的结构
AdjustDwon(a, i, 0);
}
}
六、快速排序
一趟:就是将选定的keyi调到它有序时应该在的位置,三种方法hoare版本、挖坑法、双指针法。
n躺:将每一个数都调到应该在的位置
时间复杂度:O(nlogn)
6.1 key位置选择
将数组的开头结尾中间三个位置的值比较,取中间值的位置作为key位置,这是为了防止,数组全部相同的极端案例导致快排效率低下。
//三数取中
int GetMidIndex(vector<int>& a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[right])
{
if (a[right] < a[mid])
return right;
else if (a[left] < a[mid])
return mid;
else
return left;
}
else
{
if (a[mid] < a[right])
return right;
else if (a[mid] > a[left])
return left;
else
return mid;
}
}
6.2 一趟排序的方法
hoare版本
初始版本比较难理解,我们将最左边选作key位置(将刚刚选出的key位置值和最左边位置交换,以下两种方法相同)。右指针先走找到比key值小的停下,左指针再走找到比key值大的停下,交换左右指针的值,不断循环这个过程。最终两个指针相遇的位置,再与key的位置的值交换,完成一趟排序。
int PartSort1(vector<int>& a, int left, int right)
{
int mini = GetMidIndex(a,left,right);
swap(a[mini], a[left]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
swap(a[left], a[right]);
}
swap(a[left], a[keyi]);
return left;
}
挖坑法
本质上与上一种方法相同,但是逻辑上可能更简单一些。key值位置设置为坑,右指针先走找到比key值小的停下,这时坑中放入右指针所指的值,而右指针位置成了新的坑。再走左指针找比key值大的停下,再把坑中填入左指针所指的值,左指针本身成新的坑。往复这个过程,直到左右指针相遇,往坑中填入最初的key值。完成一趟排序。
int PartSort2(vector<int>& a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
swap(a[mini], a[left]);
int key = a[left];
int pivot = left;
while (left < right)
{
while (left < right && a[right] >= key) right--;
a[pivot] = a[right];
pivot = right;
while (left < right && a[left] <= key) left++;
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
前后指针法
这是较为简单的一种方法。设置一个前指针一个后指针,前指针去找比key小的数放在后指针所指的下一个位置,一直持续,直到前指针走到最右边。在将后指针当前位置的值与key位置交换,一趟排序完成。
int PartSort3(vector<int>& a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
swap(a[mini], a[left]);
int front = left + 1;
int back = left;
int keyi = left;
while (front <= right)
{
if (a[front] < a[keyi] && ++back != front)
swap(a[front], a[back]);
front++;
}
swap(a[back], a[keyi]);
return back;
}
6.3 完整排序
采用递归分治的思想进行排序。一趟完成了一个数的排序,那么递归实现它左右两边的排序,就可以实现完整的排序。
有时情况极端,或者数据量过大,递归层次太多导致栈溢出。可以使用栈的数据结构进行快速排序的非递归实现。
void QuickSort(vector<int>& a, int left, int right)
{
if (left >= right)
return;
int mid = PartSort3(a, left, right);
QuickSort(a, left, mid - 1);
QuickSort(a, mid + 1, right);
}
// 快速排序 非递归实现
void QuickSortNonR(vector<int>& a, int left, int right)
{
stack<int> st;
st.push(left);
st.push(right);
while (!st.empty())
{
int end = st.top();
st.pop();
int beg = st.top();
st.pop();
int mid = PartSort3(a, beg, end);
if (mid + 1 < end)
{
st.push( mid + 1);
st.push( end );
}
if (mid - 1 > beg)
{
st.push(beg);
st.push(mid - 1);
}
}
}
七、归并排序
思想上是将一个数组分为两个部分,然后对两个数组一个个从头进行比较按顺序插入到新数组中去。需要保证的是分出来的左右两个数组都有序,因而又可以采用递归的方法,我们一直拆分左右两边数组,当只剩下一个或没有时,左右两边不就有序了吗。
时间复杂度:O(nlogn)
递归实现
使用函数递归的机制,分别将mid两边排序完毕后,在对mid两边的数进行归并排序。
void _MergeSort(vector<int>& a, int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
_MergeSort(a, left, mid);
_MergeSort(a, mid + 1, right);
int beg1 = left, beg2 = mid + 1;
int end1 = mid, end2 = right;
int i = left;
vector<int> temp(a.size());
while (beg1 <= end1 && beg2 <= end2)
{
if (a[beg1] < a[beg2])
temp[i++] = a[beg1++];
else
temp[i++] = a[beg2++];
}
while (beg1 <= end1)
temp[i++] = a[beg1++];
while (beg2 <= end2)
temp[i++] = a[beg2++];
for (int j = left; j <= right; j++)
a[j] = temp[j];
}
void MergeSort(vector<int>& a )
{
int n = a.size();
_MergeSort(a, 0, n - 1);
return;
}
非递归实现
非递归实现比较麻烦,由于其思想是按2,4,6,8.....这样一层层增加归并,要注意边界的修正,防止越界。
void MergeSortNonR(vector<int>& a)
{
int n = a.size();
vector<int> tmp(n);
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int beg1 = i, end1 = i + gap - 1;
int beg2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
if (end1 >= n || beg2 >= n)
break;
//修正边界
if (end2 >= n)
end2 = n - 1;
while (beg1 <= end1 && beg2 <= end2)
{
if (a[beg1] < a[beg2])
tmp[j++] = a[beg1++];
else
tmp[j++] = a[beg2++];
}
while (beg1 <= end1)
tmp[j++] = a[beg1++];
while (beg2 <= end2)
tmp[j++] = a[beg2++];
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
}