门户类网站备案,锦州网站建设动态,名城建设有限公司网站,佛山网站建设乐云seo在线制作目录 1. 基本思想
2.冒泡排序
2.1 基本思想
2.2 代码示例
2.3 冒泡排序的特性总结
3.快速排序
3.1 基本思想
#x1f335;hoare版本
#x1f335;挖坑法
编辑
#x1f335;前后指针版本
编辑
3.2 快速排序优化
#x1f33b;三数取中法选key
3.4 快速排序… 目录 1. 基本思想
2.冒泡排序
2.1 基本思想
2.2 代码示例
2.3 冒泡排序的特性总结
3.快速排序
3.1 基本思想
hoare版本
挖坑法
编辑
前后指针版本
编辑
3.2 快速排序优化
三数取中法选key
3.4 快速排序的特性总结 1. 基本思想 所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
2.冒泡排序
2.1 基本思想 冒泡排序是一种简单直观的排序算法其基本思想是通过不断比较相邻的元素并交换位置将最大或最小的元素逐步“冒泡”到最后或最前。 冒泡排序的具体步骤 比较相邻元素从数组的第一个元素开始依次比较相邻的两个元素如果顺序不对则交换它们的位置确保较大的元素向后移动。一轮冒泡经过一轮比较和交换操作最大的元素会沉到数组的最后位置。重复这个过程直到没有需要交换的元素为止。多轮冒泡重复进行上述步骤每次冒泡操作都会将当前未排序部分的最大元素移动到正确的位置。经过多轮冒泡整个数组就会逐步有序。优化可以在每一轮冒泡中记录是否有元素交换的标志如果某一轮没有元素交换说明数组已经有序可以提前结束排序。 下面是一个简单的示例演示冒泡排序的步骤 假设要排序的数组为[5, 3, 8, 2, 1] 第一轮冒泡比较并交换数组变为 [3, 5, 2, 1, 8]第二轮冒泡比较并交换数组变为 [3, 2, 1, 5, 8]第三轮冒泡比较并交换数组变为 [2, 1, 3, 5, 8]第四轮冒泡比较并交换数组变为 [1, 2, 3, 5, 8] 经过四轮冒泡排序数组变为有序状态[1, 2, 3, 5, 8]。 2.2 代码示例
//交换
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}//冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){//标志位用于记录本轮是否发生了元素交换bool flag false;for (int j 0; j n - i - 1; j){if (a[j 1] a[j]){//交换相邻元素Swap(a[j 1], a[j]);flag true;}}//如果本轮没有发生元素交换说明数组已经有序提前结束排序if (!flag)break;}
}//打印
void PrintSort(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}//测试
int main()
{int a[] { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };BubbleSort(a, sizeof(a) / sizeof(int));PrintSort(a, sizeof(a) / sizeof(int));return 0;
} 2.3 冒泡排序的特性总结
时间复杂度冒泡排序的平均时间复杂度为O(n^2)最坏情况下为O(n^2)最好情况下为O(n)。因此冒泡排序对于大规模数据集并不是一个高效的选择。空间复杂度冒泡排序的空间复杂度为O(1)因为它只需要一个额外的临时变量来进行元素交换。稳定性冒泡排序是一种稳定的排序算法相同元素的相对位置在排序前后不会改变。适用场景由于冒泡排序的效率较低通常不推荐在实际应用中使用。但对于小规模数据集或者教学目的冒泡排序是一个很好的入门算法。优缺点冒泡排序的优点是实现简单代码易于理解缺点是效率低下不适用于大规模数据集。
3.快速排序
3.1 基本思想 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法它的核心思想是通过分治法来实现排序。 具体步骤如下 选择一个基准值通常选择第一个元素。将小于基准值的元素移到基准值的左边将大于基准值的元素移到基准值的右边。对基准值左右两侧的子数组分别递归地进行快速排序。 将区间按照基准值划分为左右两半部分的常见方式有
hoare版本 思想步骤 选择一个基准元素通常选择数组的中间元素。使用两个指针一个指向数组的起始位置另一个指向数组的末尾位置。右指针向左移动直到找到一个小于基准元素的元素。左指针向右移动直到找到一个大于基准元素的元素。左右指针分别找到元素后交换它们各自位置的数值。重复步骤3到步骤5直到左指针和右指针相遇将该位置的值与基准元素位置的值交换。此时基准元素左边的元素都小于等于它右边的元素都大于等于它。递归地对基准元素左右两边的子数组进行快速排序。 //交换
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}//快速排序
void QuickSort(int* a, int begin, int end)
{//如果子数组长度为1或0则直接返回if (begin end)return;//初始化左右指针和基准值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[right], a[left]);}//将基准元素放到正确的位置上Swap(a[left], a[keyi]);keyi left;//递归的对基准元素左右两侧的子数组进行快速排序QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}//打印
void PrintSort(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}//测试
int main()
{int a[] { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintSort(a, sizeof(a) / sizeof(int));return 0;
} 挖坑法 思想步骤 先将第一个数据存放在临时变量key中形成一个坑位。right开始向前移动找比key位置小的值找到后将right位置的值放进坑里此时right位置作为新的坑。left开始向后移动找比key位置大的值找到后将left位置的值放进坑里此时left位置作为新的坑。right接着向前找left接着向后找直到left与right相遇。将key放入相遇时的坑里排序完毕。 // 挖坑法
int PartSort(int* a, int begin, int end)
{//选择第一个元素作为基准元素int key a[begin];int hole begin;while (begin end){//从右往左找到第一个小于基准元素的元素while (begin end a[end] key){--end;}//将找到的元素填入左边的坑a[hole] a[end];//更新坑的位置hole end;//从左往右找到第一个大于基准元素的元素while (begin end a[begin] key){begin;}//将找到的元素填入右边的坑a[hole] a[begin];//更新坑的位置hole begin;}//将基准元素放入最终的坑a[hole] key;return hole;
}void QuickSort(int* a, int begin, int end)
{//如果子数组长度为1或0则直接返回if (begin end)return;int keyi PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}//打印
void PrintSort(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}//测试
int main()
{int a[] { 1, 5, 7, 9, 0, 1, 2, 4, 8, 1, 3, 8, 6 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintSort(a, sizeof(a) / sizeof(int));return 0;
} 前后指针版本 思想步骤 选择一个基准元素作为key通常选择数组的第一个元素。使用两个指针前指针prev指向序列开头后指针cur指向prev指针的后一个位置。判断cur指针指向的数据是否小于key若小于则prev指针后移一位注意prev只有在cur找到比key小的数时才加1并将cur指向的内容与prev指向的内容交换然后cur指针。若大于则cur指针。依次类推直到cur遍历完整个数组最后将prev位置的值与key位置的值进行交换则完成单趟排序。 //交换
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}//前后指针法
int PartSort(int* a, int begin, int end)
{int key begin;int prev begin;int cur prev 1;while (cur end){//如果cur位置的值小于key位置的值//并且prev位置后的值如果和cur位置的值不相等//就交换prev位置和cur位置的值if (a[cur] a[key] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[key]);key prev;return key;
}void QuickSort(int* a, int begin, int end)
{//如果子数组长度为1或0则直接返回if (begin end)return;int keyi PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 3.2 快速排序优化
三数取中法选key 三数取中法是在快速排序算法中用于选择基准元素的一种策略。它的思想是从待排序数组中随机选择三个元素然后取它们的中间值作为基准元素这样可以尽量避免选择到极端的值作为基准元素从而提高快速排序的效率。 使用三数取中法选择基准元素的具体步骤 从待排序数组中随机选择三个元素通常是选择数组的第一个元素、中间元素和最后一个元素。比较这三个元素找到它们的中间值作为基准元素。可以使用简单的比较排序或者其他方法来找到中间值。将选定的基准元素放置在数组的最左边或者其他位置并记录其值。接下来的快速排序过程中使用这个选定的基准元素进行分区操作将小于基准元素的元素放在左边大于基准元素的元素放在右边。 使用三数取中法选择基准元素可以有效地避免选择到极端值作为基准元素从而提高快速排序的效率减少最坏情况下的时间复杂度。这种方法在实际应用中被广泛采用用以提高快速排序的性能。 代码示例
//交换
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}//三数取中
int GetMidi(int* a, int begin, int end)
{//选择三个元素的中间值作为基准元素int midi (begin end) / 2;//确保 a[begin] a[midi] a[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;}
}//快速排序
void QuickSort(int* a, int begin, int end)
{//如果子数组长度为1或0则直接返回if (begin end)return;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[right], a[left]);}//将基准元素放到正确的位置上Swap(a[left], a[keyi]);keyi left;//递归的对基准元素左右两侧的子数组进行快速排序QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}//测试
int main()
{int a[] { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintSort(a, sizeof(a) / sizeof(int));return 0;
}
3.4 快速排序的特性总结 时间复杂度平均时间复杂度为O(N*logN)最坏情况下为O(N^2)最好情况下为O(N*logN)。空间复杂度快速排序是一种原地排序算法不需要额外的存储空间空间复杂度为O(1)。稳定性快速排序是一种不稳定的排序算法即相同元素的相对位置可能会发生变化。分治思想快速排序使用分治思想将数组分为两部分分别对左右子数组进行排序。
