|
?
?
活动地址：CSDN21天学习挑战赛
冒泡排序
算法思想，进行n-1趟外循环，也即是第一次将数组的最大值移动到数组尾部，第二次就是第二大，进行n-1次循环是因为每次一个最后进行n-1次之后最后一个元素的位置也就固定了。内循环就是比较两个元素的大小，将大的元素放到小元素的后面，每次循环之后比较的元素就减去一个，因为循环完一次就有一个数组最大值移动到了数组的尾部。
这里加入标志位flag，如果某次循环没有数组元素交换，那么这个数组就已经是有序了
代码实现如下：
#include<stdio.h>
int main()
{
int arr[10] = { 32,5,66,77,7,4,97,4,3,0 };
int flag = 0;
for (int i = 1; i < 10; i++)
{
flag = 0;
for (int j = 0; j < 10 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = tmp;
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
return 0;
}
冒泡排序是一个简单的排序算法，写起来很简单，两层for循环搞定，但是这也是一个效率很低的排序算法，无论时在什么情况下他的时间复杂度都是O（N^2)所以在追求效率的代码中不适合使用该算法。
快速排序
快速排序版本1：挖坑法
排序思想：先确定一个关键字key（一般选第一个或者最后一个），然后以该位置为坑，然后通过左右指针开始遍历数组，先在右边找到小于key的值，放到坑里面，然后right变为新的坑，再去左边，找一个大于key的值，放到坑里面，然后left变为新的坑，直到最后left==right跳出循环，这时候再将key放到pivot位置，该位置就是key的最终位置，然后使用分治思想，如果pivot左边时有序的，右边也是有序的那么数组就有序了，所以递归左区间，递归右区间，完成排序。
快速排序类似，二叉树的前序遍历，先解决根，再解决左右子区间（子树）
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
int key = arr[begin];
int pivot = begin;
while(left < right)
{
while(begin< right && arr[right] >= key)
{
--right;
}
arr[pivot] = arr[right];
pivot = right;
while(left < right && arr[begin] <= key)
{
++left;
}
arr[pivot] = arr[left];
pivot = left;
}
arr[pivot] = key;
QuickSort(arr, begin, pivot - 1);
QuickSort(arr, pivot + 1, end);
}
快排优化版本(三数取中and小区间优化)
因为我们知道上述快排在极限情况下，比如数组是有序的，每次选取，选左区间就会遍历右区间，这样快速排序的二分就失效了，所以这时候时间复杂度是O（N^2),这时候我们可以使用三数取中法进行优化，就是进入一趟排序之前，先将区间中间位置，开始位置，结束位置，他们三个数的中间大小的那个数与第一个数字交换，这样如果数组是有序的，就可以避免最坏情况的出现，因为每次将数组中间那个值换到begin的位置当作key，就可以使得每次排序后接近二分。
但是可能有人还会想这样一个问题，比如，多加了一个求三数取中的函数，函数的调用栈帧的创建是不是会增加时间的消耗呢？例如100w个数，会多100w次函数调用，说答案，其实是不会的，因为cpu对于函数调用的优化是很快的，就算是多调用了100w次，也不会差距几毫秒，但是对于这个问题，我们还有一个优化，就是小区间优化，比如我们递归的时候100w个数，每次二分到最后三次的时候，会产生219+218+2^17次调用（二叉树最后三层个数计算）这就是占据了80%以上的函数调用，这时候，我们可以进行小区间优化，当区间个数小于10的时候采用InsertSort，大于10，采用快排。就可以了。
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
return;
int index = midnum(arr, begin, end);
Swap(&arr[begin], &arr[index]);
int left = begin;
int right = end;
int key = arr[begin];
int pivot = begin;
while(left < right)
{
while(left< right && arr[right] >= key)
{
--right;
}
arr[pivot] = arr[right];
pivot = right;
while(left < right && arr[left] <= key)
{
++left;
}
arr[pivot] = arr[left];
pivot = left;
}
pivot = left;
arr[pivot] = key;
if ((pivot - 1 - begin+1) > 10)
{
QuickSort(arr, begin, pivot - 1);
}
else
{
InsertSort(arr + begin, pivot - 1 - begin + 1);
}
if ((end - pivot - 1 + 1) > 10)
{
QuickSort(arr, pivot + 1, end);
}
else
{
InsertSort(arr + pivot + 1, end - pivot - 1 + 1);
}
}
快速排序版本2：左右指针法
因为左右指针法和挖坑法，在第一次排完序之后各个数字的位置不同，在选择题中可能会遇到，所以这里我会都介绍一下的。能写出一种即可。
void QuickSort2(int* arr, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
int key = left;
while (left < right)
{
while (left < right && arr[right] >= arr[key])
right--;
while (left < right && arr[left] <= arr[key])
++left;
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key], &arr[left]);
QuickSort2(arr, begin, left - 1);
QuickSort2(arr, left+1, end);
}
快速排序版本3：前后指针法
首先定义一个前指针prev，然后一个在后面的指针cur，cur先移动，去数组后面找小于arr[keyi]的值，找到了就++prev然后交换prev位置的值和cur位置的值，相当于是把小于key的值向前扔，大于key的值向后扔。最后cur走到数组尾部，prev指向最后一个小于key的值，将arr[keyi]于arr[prev]交换即可。
void QuickSort3(int* arr, int begin, int end)
{
if (begin >= end)
return;
int index = midnum(arr, begin, end);
Swap(&arr[begin], &arr[index]);
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
while (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
Swap(&arr[keyi], &arr[prev]);
QuickSort3(arr, begin, prev - 1);
QuickSort3(arr, prev + 1, end);
}
|