成都优化网站源头厂家,南京工程网站建设,网站开发 外包,西地那非副作用太强了#x1f497;个人主页#x1f497; ⭐个人专栏——数据结构学习⭐ #x1f4ab;点击关注#x1f929;一起学习C语言#x1f4af;#x1f4ab; 目录 导读#xff1a;数组打印与交换1. 交换排序1.1 基本思想#xff1a;1.2 冒泡与快排的异同 2. 冒泡排序2.1 基本思想2.2 … 个人主页 ⭐个人专栏——数据结构学习⭐ 点击关注一起学习C语言 目录 导读数组打印与交换1. 交换排序1.1 基本思想1.2 冒泡与快排的异同 2. 冒泡排序2.1 基本思想2.2 实现代码 3. 快速排序3.1 基本思想3.2 hoare版本3.2.1 动图讲解3.2.2 实现代码3.2.3 代码优化 3.3 挖坑法3.3.1 动图详解3.3.2实现代码 3.4 双指针3.4.1 动图详解3.4.2 实现代码 4. 无递归实现快排4.1 基本思想4.2 实现代码 导读
我们在前面学习了排序包括直接插入排序希尔排序选择排序堆排序。 今天我们来学习交换排序也就是冒泡排序和快排。 下期我们来讲一讲归并排序。 关注博主或是订阅专栏掌握第一消息。
数组打印与交换
为了方便我们来测试每个排序是否完成我们来写个打印数组和交换两数的函数方便我们后续的打印与交换。
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}1. 交换排序
1.1 基本思想
所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 交换排序包括冒泡排序与快速排序。
1.2 冒泡与快排的异同
相似之处 都是基于比较的排序算法通过比较元素的大小来确定它们的顺序。 不同之处 思想不同冒泡排序是通过相邻元素的比较和交换来将较大的元素“浮”到序列的末尾而快速排序是通过在序列中选择一个基准元素将序列分割成两个子序列并递归地对子序列进行排序。 时间复杂度不同冒泡排序的平均时间复杂度为O(n2)最好情况下为O(n)最坏情况下为O(n2)。快速排序的平均时间复杂度为O(nlogn)最坏情况下为O(n^2)。 空间复杂度不同冒泡排序的空间复杂度为O(1)原地排序。快速排序的空间复杂度为O(logn)需要使用递归栈空间。 稳定性不同冒泡排序是稳定的排序算法相等元素的相对顺序不会改变。快速排序是不稳定的排序算法相等元素的相对顺序可能会改变。 总结冒泡排序和快速排序都是基于比较的排序算法它们的主要区别在于思想、时间复杂度、空间复杂度和稳定性等方面。快速排序通常比冒泡排序更高效但在某些情况下冒泡排序可能更适合例如对较小规模的数据进行排序。
2. 冒泡排序
2.1 基本思想
冒泡排序算法的基本思想是要将待排序序列中的元素逐个比较并交换位置使得较大的元素逐渐“浮”到序列的末尾。 从待排序序列的第一个元素开始逐个比较相邻的两个元素。 如果前一个元素比后一个元素大则交换它们的位置。这样就使得较大的元素逐渐“浮”到序列的末尾。 继续对剩下的元素重复上述比较和交换的过程直到整个序列有序为止。 重复上述步骤每次将待排序序列的长度减1直到待排序序列的长度为1。 冒泡排序算法的思想类似于水中冒泡较大的元素会逐渐向上浮动而较小的元素会逐渐沉淀到底部。因此最终结果是将待排序序列从小到大排序。
冒泡排序算法的时间复杂度为O(n^2)其中n为待排序序列的长度。尽管冒泡排序算法的效率相对较低但由于其实现简单适用于数据量较小的情况。
2.2 实现代码
// 冒泡排序
void BubbleSort(int* a, int n)
{int i 0;int j 0;for (i 0; i n; i){for (j 0; j n - i -1; j){if (a[j 1] a[j]){Swap(a[j 1], a[j]);}}}
}
void TestBubbleSort()
{int arr[10] { 5, 1, 8, 7, 3, 9, 2, 0, 4, 6 };int sz sizeof(arr) / sizeof(arr[0]);BubbleSort(arr, 10);PrintArray(arr, 10);
}
int main()
{TestBubbleSort();return 0;
}3. 快速排序
快速排序有三种实现方法
hoare版本挖坑法双指针
3.1 基本思想
快速排序是一种基于分治思想的排序算法其基本思想可以概括为以下步骤 选择一个基准元素从待排序序列中选择一个元素作为基准元素。 分割操作以基准元素为准将序列分割成两个子序列使得左边的子序列中的所有元素都小于等于基准元素右边的子序列中的所有元素都大于基准元素。这个分割操作可以采用多种方式实现常见的有挖坑法、交换法和指针交替法等。 递归排序对分割后的两个子序列分别递归地进行快速排序直到子序列的长度为1或0即递归的终止条件。 合并操作将分割后的子序列进行合并即将左边子序列、基准元素和右边子序列按照顺序拼接起来得到完整的排序序列。 整个过程可以通过递归来实现每次递归中选取一个基准元素将序列分割成两部分然后递归地对两部分进行排序最后将结果合并起来得到有序序列。
快速排序的时间复杂度为O(nlogn)其中n为待排序序列的长度。在最坏情况下快速排序的时间复杂度为O(n^2)但通常情况下快速排序是一种高效的排序算法。快速排序是原地排序的算法不需要额外的空间。然而由于快速排序是递归实现的所以需要使用递归栈空间。
3.2 hoare版本
3.2.1 动图讲解
我们需要定义一个key来指向第一个数也就是基准元素。 同时定义left和right来指向数组的两端。 我们让right先走来找比key小的值找到后left开始走去找比key大的值找到之后交换left和right的值之后继续right找小left找大直到两者相遇循环结束。 这时再把key处的值和left处的值交换让key走到left位置。 第一次循环结束后如图 左边的值都比key处的值小而右边的值都比key处的值大。 这时key所指向的值就是我们上面所说的基准元素。 下面我们就需要以key为中点分为左右两个序列。 然后我们可以用递归继续调用这个函数分别把左子序列和右子序列继续排序划分为若干左右子序列这样就能实现排序。
3.2.2 实现代码
递归结束条件就是当第n个子序列长度为1或者0时结束也就是子序列起点和尾点重合。
void QuickSort1(int* a, int begin, int end)
{if (begin end){return;}int key begin;int left begin;int right end;while (left right){// 右边先走找比key值小的while (right left a[right] a[key]){right--;}// 左边后走找比key值大的while (right left a[left] a[key]){left;}Swap(a[left], a[right]);}Swap(a[key], a[left]);key left;//分左右两边//左边QuickSort1(a, begin, key - 1);//右边QuickSort1(a, key 1, end);
}
void TestQuickSort1()
{int arr[10] { 5, 1, 8, 7, 3, 9, 2, 0, 4, 6 };int sz sizeof(arr) / sizeof(arr[0]);QuickSort1(arr, 0, sz - 1);PrintArray(arr, 10);
}
int main()
{TestQuickSort1();return 0;
}3.2.3 代码优化
如果我们遇到一些极端的情况比如数组是以排序好或者逆序这可能就会使我们的时间复杂度大大增加以及递归调用的太多可能会导致Stack Overflow的情况。 我们就可以在keyleft和right三者中选择一个中位数来当key值。 还有比如数据较少的情况下选择快排是不大理想的这时我们用直接插入排序效果会更好。
//优化
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin midi end 三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else // a[begin] a[midi]{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}// hoare
void QuickSort1(int* a, int begin, int end)
{if (begin end){return;}if (end - begin 1 10){InsertSort(a begin, end - begin 1);}else{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key begin;int left begin;int right end;while (left right){// 右边先走找比key值小的while (right left a[right] a[key]){right--;}// 左边后走找比key值大的while (right left a[left] a[key]){left;}Swap(a[left], a[right]);}Swap(a[key], a[left]);key left;//分左右两边//左边QuickSort1(a, begin, key - 1);//右边QuickSort1(a, key 1, end);}}
void TestQuickSort1()
{int arr[10] { 5, 1, 8, 7, 3, 9, 2, 0, 4, 6 };int sz sizeof(arr) / sizeof(arr[0]);QuickSort1(arr, 0, sz - 1);PrintArray(arr, 10);
}
int main()
{TestQuickSort1();return 0;
}3.3 挖坑法
3.3.1 动图详解
挖坑法与hoare版本的快排并无太大差别。 我们另定义一个hole变量left和right不变这时的key不再是下标而是一个具体的数值key是首元素的值。 我们仍旧是右边先找小找到之后并不是直接让左边去找大而是让这个小的值赋值给hole的位置注意不是交换key的值记录着最开始的hole位置的值不必担心丢失。 接着让hole移动到right位置左边开始找大找到后也是把left指向的值赋值给hole位置hole移动到left位置。 仍旧是left和right相遇之后把key记录的值赋值给hole位置。
3.3.2实现代码
//挖坑法
void QuickSort2(int* a, int begin, int end)
{if (begin end){return;}int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin;int right end;int hole left;int key a[hole];while (left right){while (a[right] key right left){right--;}a[hole] a[right];hole right;while (a[left] key right left){left;}a[hole] a[left];hole left;}a[hole] key;QuickSort2(a, begin, hole - 1);QuickSort2(a, hole 1, end);
}void TestQuickSort2()
{int arr[10] { 5, 1, 8, 7, 3, 9, 2, 0, 4, 6 };int sz sizeof(arr) / sizeof(arr[0]);QuickSort2(arr, 0, sz - 1);PrintArray(arr, 10);
}
int main()
{TestQuickSort2();return 0;
}3.4 双指针
3.4.1 动图详解
双指针相对于上面两个代码是相较少的不必再去三位取中。 定义两个指针curprev而key仍然是值。 开始的时候两个指针都指向第一个元素 之后cur先走找比key值小的数找到之后prev向前走一步如果这时prev和cur的指向的不是同一个元素就交换两者指向的值。 反之如果两者重叠cur则继续往前走一步。 直到cur出了数组循环结束这时再交换key值和prev。 再以prev为中心分为左右子序列。
3.4.2 实现代码
// 双指针
void QuickSort3(int* a, int begin, int end)
{if (begin end){return;}int key begin;int prev begin;int cur prev 1;while (cur end){if (a[cur] a[key] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[key], a[prev]);QuickSort3(a, begin, prev - 1);QuickSort3(a, prev 1, end);
}
void TestQuickSort3()
{int arr[10] { 5, 1, 8, 7, 3, 9, 2, 0, 4, 6 };int sz sizeof(arr) / sizeof(arr[0]);QuickSort3(arr, 0, sz - 1);PrintArray(arr, 10);
}
int main()
{TestQuickSort3();return 0;
}4. 无递归实现快排
4.1 基本思想
非递归实现快速排序算法的关键是使用栈来模拟递归过程。具体步骤如下 创建一个栈并将待排序数组的起始索引和结束索引入栈。循环直到栈为空 弹出栈顶的起始索引和结束索引作为当前子数组的范围。选择一个基准元素将数组按照基准元素进行划分得到基准元素的索引。如果基准元素左侧的子数组长度大于1则将左侧子数组的起始索引和结束索引入栈。如果基准元素右侧的子数组长度大于1则将右侧子数组的起始索引和结束索引入栈。 返回排序后的数组。 4.2 实现代码
前面我们都是用递归的方法来实现快排的思考一下不用递归该怎么写。 这里我们可以用栈来实现我们每次把需要排列的左右子序列的开始和结束的下标入栈记录范围之后再出栈赋给left和right又或者其它变量最后调用上面的函数来实现排序。 我们先来看代码后面来具体分析。 在这里的栈我还是调用之前写的栈代码感兴趣的小伙伴可以看数据结构的专栏。
// hoare
int PartSort1(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;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;
}
//挖坑法
int PartSort2(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin;int right end;int hole left;int key a[hole];while (left right){while (a[right] key right left){right--;}a[hole] a[right];hole right;while (a[left] key right left){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}
//双指针
int PartSort3(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key begin;int prev begin;int cur prev 1;while (cur end){if (a[cur] a[key] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[key], a[prev]);key prev;return key;
}
//无递归方法实现
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(s);STPush(s, end);STPush(s, begin);while (!STEmpty(s)){int left STTop(s);STPop(s);int right STTop(s);STPop(s);int keyi PartSort3(a, left, right);// [left, keyi-1] keyi [keyi1, right]if (left keyi - 1){STPush(s, keyi - 1);STPush(s, left);}if (keyi 1 right){STPush(s, right);STPush(s, keyi 1);}}STDestroy(s);
}
