湛江网站设计服务,为网站做seo需要什么软件,空间站对接,网站的建设方法包括什么前言
前两期我们已经对插入排序#xff08;直接插入排序和希尔排序#xff09; 和 选择排序#xff08;直接选择排序和堆排序#xff09;进行了详细的介绍~#xff01;这一期我们再来详细介绍一组排序 #xff1a;交换排序即耳熟能…前言
前两期我们已经对插入排序直接插入排序和希尔排序 和 选择排序直接选择排序和堆排序进行了详细的介绍~这一期我们再来详细介绍一组排序 交换排序即耳熟能详的冒泡排序和赫赫有名的快速排序~
本期内容介绍 冒泡排序 快速排序Hoare、挖坑、前后指针、非递归 交换排序的基本思想 对待排序的序列进行元素的两两比较如果满足交换条件交换。即将元素逐步换到合适的位置~ 冒泡排序 从前往后逐一比较相邻元素前面的大于或小于后面的则进行交换每一轮将当前轮最大或最小的元素冒泡到当前论的最后。重复上述过程最后就是有序的~ OK还是画个图理解一下 OK这就是冒泡排序的过程我们还是先来写单趟再来改造整体
单趟 //注意前一个和后一个比j最大只能走到n-2(倒数第二个)j1只能走到n-1(倒数第一个)for (int j 0; j n - 1; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}
整体
整体的话控制一下每一趟的交换个数即可~
//冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i)//n-1是最后一个只能放在第一个即可以不对他排{//注意前一个和后一个比j最大只能走到n-2(倒数第二个)j1只能走到n-1(倒数第一个)for (int j 0; j n - 1 - i; j)//每一趟确定当前趟的最大之到当前趟的最后{ //每一趟确定出一个即每一趟少排i个if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
}
OK 测试一下看结果 没问题但有一种情况就是上述画图的那种例子已经有序了但不知道还是在两两比较。这其实是很没有必要的~请我们可以优化一下 优化思路在每一趟开始之前进行一个有序的标记当一趟结束后判断该标记如果有序直接不用再往后排了否则继续进行排序~ //冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i)//n-1是最后一个只能放在第一个即可以不对他排{int flag 1;//假设该趟有序//注意前一个和后一个比j最大只能走到n-2(倒数第二个)j1只能走到n-1(倒数第一个)for (int j 0; j n - 1 - i; j)//每一趟确定当前趟的最大之到当前趟的最后{ //每一趟确定出一个即每一趟少排i个if (a[j] a[j 1]){Swap(a[j], a[j 1]);flag 0;//交换了说明是该趟是无序的}}if (flag 1)//说明已经有序了没有必要再冒泡了{break;}}
}
冒泡这是一种写法其实还有很多。这里再来一个这里前面与后面比较
单趟 //后一个和前一个比较j最大走到倒数第一个for (int j 1; j n - i; j){if (a[j - 1] a[j])//后面与前一个比较{Swap(a[j - 1], a[j]);flag 0;}}
整体
//冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int flag 1;//后一个和前一个比较j最大走到倒数第一个for (int j 1; j n - i; j){if (a[j - 1] a[j])//后面与前一个比较{Swap(a[j - 1], a[j]);flag 0;}}if (flag 1)//已经有序不要再去冒泡了{break;}}
}
测试一下 一点问题没有~ 总结冒泡虽然简单但一定要注意边界点的控制~ 复杂度分析 时间复杂度O(N^2) 每一趟遍历选出一个最值即每一趟都比前一趟少比较一次所以他应该是第一趟比较n-1次第二趟比较n-2次...1很明显这是等差数列求和最后的时间复杂度为O(N^2) 空间复杂度O(1) 快速排序 在一个序列中先随意选出一个元素该元素称为基准。比基准值大的移动到基准的右边比基准值小的移动到基准的左边这样基准值就到了他该到的位置。然后对基准值的左右区间分别进行上述相同的操作 相信看到这里应该想到快排用的是递归是的但我们也会实现非递归版本~ 快排最核心的就是他选基准的那个单趟这里的版本我会的有三个Hoare、挖坑法、前后指针。下面一个一个的来
Hoare 选择最左端或最右端作为基准点使用两个指针从序列两端向中间扫描右指针找到比基准小的值左指针找到比基准大的值然后进行交换。重复这个过程直到左右指针相遇相遇的位置就是基准的最终位置。为什么相遇的位置就是最终的位置呢后面会解释 OK还是画个图理解一下 OK上代码
//Hoare
int PartSort1(int* a, int left, int right)
{int keyi left;//选最左端的为基准while (left right){//右指针找小while (left right a[right] a[keyi])right--;//左指针找大while (left right a[left] a[keyi])left;//找到了交换Swap(a[right], a[left]);}//当相遇时left或right与基准交换Swap(a[left], a[keyi]);return left;//返回基准下标
} 解释 1、这里找大或找小时可能在极端情况下找不到从而导致越界。所以得判断让其不要越界~ 2、为什么在左右指针相遇时就是基准的最终位置左右指针相交有两种情况左找右和右找左 左找右因为是右先找小所以当他们相交时一定是小于基准的。 右找左因为前一轮已经交换过所以当前左一定是小于基准的的。 这就保证了当左右相交时的位置与基准的位置交换后基准的位置是最终位置 OK单趟写好了就可以用相同的方式去处理左右区间了~而每个区间的处理和上述的处理方式一样所以使用递归就很方便~ 我们以前在函数那一期介绍递归的时候说过递归必须有结束条件~这个的结束条件是啥吧呢 其实很简单只需要注意每次递归的那个区间合法即可即左区间 右区间(相等只有一个元素也不需要排了) 整体
//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort1(a, begin, end);//[begin, key-1] key [key1, end]QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}测试一把 其实介绍到这里你有没有感觉到。快排很像二叉树的前序遍历~ OK我们再来看看Hoare的优化版(国人优化的)挖坑法
挖坑法 和Hoare的很相似。用左右两指针向中间扫描右找小左找大。选最左端或最右端为基准基准位置空出来了形成了坑。右指针(左指针)先走找到小(大)的了填到左(右)边坑里面。自身形成了坑左(右)边找大(小)填到右(左)边的坑。如此循环直到相交然后把基准与左右指针的任意交换即可~ OK还是画个图 OK上代码
//挖坑法
int PartSort2(int* a, int left, int right)
{int keyi a[left];//选左端为基准左端就是坑位while (left right){//右指针找小while (left right a[right] keyi)right--;a[left] a[right];//找到了填到左坑自身成了新坑位//左指针找大while (left right a[left] keyi)left;a[right] a[left];//找到了填到右坑自身成了新坑位}//左右指针相遇交换基准与左右指针的任意Swap(a[left], keyi);return left;//返回基准的下标
}
整体
//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort2(a, begin, end);//[begin, key-1] key [key1, end]QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}
测试一下 OK没有问题下面我们在来看一个版本~前后指针。
前后指针 选左端为基准前指针在第一个位置后指针的第二个位置。当前指针遇到小于基准值时当前位置的值与后指针的下一个位置的值进行交换。直到前指针到区间结束此时后指针与基准交换后指针的位置就是最终基准的位置 OK还是来画个图 OK上代码
//前后指针
int PartSort3(int* a, int left, int right)
{int prev left;//后(慢)指针int keyi left;//基准int cur left 1;//快指针while (cur right)//闭区间所以是{if (a[cur] a[keyi])//快指针如果找到小了{Swap(a[prev], a[cur]);//与prev的下一个位置交换}cur;}Swap(a[prev], a[keyi]);//最后交换基准位置与prev位置的值return prev;//返回基准的位置
} 这里其实可以小小的优化一下和上面画图情况的一样假设prev和cur是同一个位置时是不是根本就不用交换啊~OK我们可以控制一下 //前后指针
int PartSort3(int* a, int left, int right)
{int prev left;//后(慢)指针int keyi left;//基准int cur left 1;//快指针while (cur right)//闭区间所以是{if (a[cur] a[keyi] prev ! cur)//快指针如果找到小了并且prev的位置和cur不同{Swap(a[prev], a[cur]);//与prev的下一个位置交换}cur;}Swap(a[prev], a[keyi]);//最后交换基准位置与prev位置的值return prev;//返回基准的位置
}整体
//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort3(a, begin, end);//[begin, key-1] key [key1, end]QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}
测试一下 OK没有问题~ 以上就是三个版本快排了他们都是递归版本的。以前介绍的递归时说过递归有个致命的缺陷是如果递归的太深会栈溢出每一次调用都要建立函数栈帧一般的情况下栈区的大小时7M左右~为了解决栈溢出的问题我们采用非递归即迭代的方式来解决这个问题~下面我们来实现一下~ 非递归版本 非递归版本其实时利用栈来模拟递归的这个过程的~但C语言没有栈这种数据结构...得手搓我们就把以前的在栈和队列那一期的那个拿过来。 实现思路模拟递归的方式先让数组的 0 和 size-1 即左右端点的下标入栈当栈不为空时分别取栈顶元素赋值给左右指针。然后调用任意一个版本的单趟获得基准然后把基准左右的两个区间入栈继续上述操作直到栈为空就排序结束了~ OK画个图 OK上代码
//快速排序 非递归版
void QuickSort(int* a, int begin, int end)
{ST* s NULL;//先把左右区间入栈Push(s, end);Push(s, begin);//栈不为空时出left和rightwhile (!STEmpty(s)){//获取左端点int left STTop(s);Pop(s); //获取右端点int right STTop(s);Pop(s);//获取该区间的基准int keyi PartSort3(a, left, right);//右子区间入栈if (keyi 1 right){Push(s, right);Push(s, keyi 1);;}//左子区间入栈if (left keyi - 1){Push(s, keyi-1);Push(s, left);}}STDestory(s);
}
OK测试一下 分析以及优化 我们前面说过快速排序和二叉树的前序遍历很象然而上述的版本的单趟和一些情况下其实可以做一下一些小优化~第一当我们的待排序的序列是已经有序的时我们快速排序的时间复杂度时很高的接近O(n^2)如下图1分析避免这种情况我们采用三数取中的方式来解决。第二递归的最后几层是整个递归的80%左右而递归要建立函数栈帧空间消耗比较大我们可以在区间小的时候换成直接插排提高效率~ 图1快排最差情况已经有序 解决已经有序的序列排序效率低的问题 ---三数取中 三数取中当前待排的序列的最左端、最右端、最中间。三个值中取中间大的那一个~这样就不怕有序的情况效率低了而且是越有序越效率高~ 代码实现
//三数取中
int GetMid(int* a, int left, int right)
{int mid left (right - left) / 2;if (a[left] a[right]){if (a[mid] a[right]){return right;}else if (a[mid] a[left]){return left;}elsereturn mid;}else{//left rightif (a[mid] a[right]){return right;}else if (a[mid] a[left]){return left;}elsereturn mid;}
} 当区间小的时候我们可以采用指直接插排来优化。 原因在序列很大时当区间小的时候就说明此小区间已经接近有序了而接近有序的区间直接插入排序的效率很高的。 代码实现
void QuickSort(int* a, int begin, int end)
{if (begin end)return;if (end - begin 1 10){int key PartSort1(a, begin, end);//[begin, key-1] key [key1, end]QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);}else{InsertSort(a, end - begin 1);//区间小于10个待排序的元素后进行直接插排}
}
复杂度分析 时间复杂度O(N*logN) 快排可以看做一棵二叉树一共有N个节点。每一层确定2^(i-1)i从1开始个待排元素的最终位置总共的确定待排的层数是2^x N --- x logN,而每一次确定一个元素的位置又是遍历一遍待排的序列即O(N)所以总共合计O(N*logN) 注意加了三数取中几乎不可能再出现O(N^2)了 空间复杂度O(logN) 因为递归是要开销栈帧的我们前面在复杂度的那一期介绍过空间可以重复利用而时间不可重复利用。所以这里至多递归到他的深度即h logN,所以他的空间复杂度是O(logN) 注意非递归的空间复杂度任然是log(N)原因是他的空间消耗虽然不在栈了但他利用栈的数据结构转移到了堆上还是会消耗空间的~ 优化后的快排源码
//三数取中
int GetMid(int* a, int left, int right)
{int mid left (right - left) / 2;if (a[left] a[right]){if (a[mid] a[right]){return right;}else if (a[mid] a[left]){return left;}elsereturn mid;}else{//left rightif (a[mid] a[right]){return right;}else if (a[mid] a[left]){return left;}elsereturn mid;}
}Hoare
O(N)
int PartSort1(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], 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;
}挖坑法
O(N)
int PartSort2(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int keyi a[left];while (left right){while (left right a[right] keyi)right--;a[left] a[right];while (left right a[left] keyi)left;a[right] a[left];}a[left] keyi;return left;
}前后指针
O(N)
int PartSort3(int* a, int left, int right)
{int mid GetMid(a, left, right);Swap(a[mid], a[left]);int prev left;//后(慢)指针int keyi left;//基准int cur left 1;//快指针while (cur right)//闭区间所以是{//if (a[cur] a[keyi])//快指针如果找到小了//{// Swap(a[prev], a[cur]);//与prev的下一个位置交换//}if (a[cur] a[keyi] prev ! cur)//快指针如果找到小了并且prev的位置和cur不同{Swap(a[prev], a[cur]);//与prev的下一个位置交换}cur;}Swap(a[prev], a[keyi]);//最后交换基准位置与prev位置的值return prev;//返回基准的位置
}//快速排序
//O(N*logN)
void QuickSort(int* a, int begin, int end)
{if (begin end)return;if (end - begin 1 10){int key PartSort1(a, begin, end);//[begin, key-1] key [key1, end]QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);}else{InsertSort(a, end - begin 1);//区间小于10个待排序的元素后进行直接插排}
}//快速排序 非递归版
//void QuickSort(int* a, int begin, int end)
//{
// ST* s NULL;
// //先把左右区间入栈
// Push(s, end);
// Push(s, begin);
//
// //栈不为空时出left和right
// while (!STEmpty(s))
// {
// //获取左端点
// int left STTop(s);
// Pop(s);
// //获取右端点
// int right STTop(s);
// Pop(s);
// //获取该区间的基准
// int keyi PartSort3(a, left, right);
// //右子区间入栈
// if (keyi 1 right)
// {
// Push(s, right);
// Push(s, keyi 1);;
// }
// //左子区间入栈
// if (left keyi - 1)
// {
// Push(s, keyi-1);
// Push(s, left);
// }
// }
//
// STDestory(s);
//}
OK好兄弟我们本期分享就到这里我们下一期的归并排序再见~
