电商主图设计网站,wap手机网站模板,义乌做网站的,手机网站会员中心模板下载宝子#xff0c;你不点个赞吗#xff1f;不评个论吗#xff1f;不收个藏吗#xff1f; 最后的最后#xff0c;关注我#xff0c;关注我#xff0c;关注我#xff0c;你会看到更多有趣的博客哦#xff01;#xff01;#xff01; 喵喵喵#xff0c;你对我真的很重要… 宝子你不点个赞吗不评个论吗不收个藏吗 最后的最后关注我关注我关注我你会看到更多有趣的博客哦 喵喵喵你对我真的很重要。 前言 小喵喵课堂开课来今天我们学习七个常见的排序哦哦耶 喵喵今天也要加油哦 来吧不乱叫上导图 目录
前言
八大经典排序的概述
直接插入排序
希尔排序
选择排序
堆排序
冒泡排序
快速排序(快排
归并排序
总结 ┗|O′|┛ 嗷~~怎么能忘了基数排序呢补上补上
八大经典排序的概述 八大排序算法是指常见的八种经典排序算法它们分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。 冒泡排序比较相邻的元素如果顺序错误就交换它们重复这个过程直到整个数组有序。选择排序每次从待排序的数组中选择最小或最大的元素放在已排序数组的末尾直到整个数组有序。插入排序遍历数组将当前元素插入已排好序的子数组中的适当位置直到整个数组有序。希尔排序通过设置间隔将数组分组对每个分组进行插入排序逐渐减小间隔直到间隔为1时进行最后一次插入排序。归并排序采用分治的思想将待排序数组划分为较小的子数组然后递归地对子数组进行排序并将排好序的子数组合并成更大的有序数组。快速排序选取一个基准元素将数组划分为左右两部分左边部分都比基准元素小右边部分都比基准元素大在递归地对左右两部分进行快速排序。堆排序将待排序数组构建成一个大顶堆然后将堆顶元素与最后一个元素交换并重新调整堆重复这个过程直到整个数组有序。基数排序根据元素的每个位上的值进行排序先按低位排序再按高位排序直到所有位都排序完成。 直接插入排序 直接插入的排序规则如图所示 将end和tmp代入进去思考一来的3就算起始点排好了位置作为end,然后tmp是44443tmpend,所以不交换位置算排好了end1tmp1。那么第二次比较end是44tmp是38endtmp交换位置38排在44前面。那么第三次比较5比44小比38小排在38前面。以此类推循环排好数组。 void InSert(int* a, int n)
{for (int i 1; i n; i){int end i - 1;int tmp a[i];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 希尔排序 希尔排序是直接插入排序的升级版先对数组进行有规律的分组分成多个组然后每个小组进行直接插入排序。每个小组排完后再进行一次直接插入排序就要轻松地多能够快速排好大大提高了排序的效率。 分成绿蓝红三组分别进行直接插入排序。 void InsertSort(int* a, int n)
{int gap 3;for (j0;jgap;j){for (int i j; i n-gap; igap){int end i;int tmp a[igap];while (end 0){if (tmp a[end]){a[end gap] a[end];end-gap;}else{break;}}a[end gap] tmp;}}}
void InsertSort(int* a, int n)
{int gap n;int j 0;while (gap 1){gap gap / 2;for (j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[i gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}} 选择排序 选择排序很直观就是要选择我们先选择3作为有序数组然后从3后面的数组中选出最小的数并于3进行比较谁小谁站在前面。2比3小2与3交换位置。依次往后推拍成有序数组。 喵很难评这是简单版的一个点移动而我们一般上的是困难版的两个点喵不好理解喵喵也是搞了好久才明白滴喵。那么让我们开始吧猫猫队冲冲冲 两个点的移动建议结合代码自己也跟着走一走感觉不就来了嘛 //这是两个点的移动
void SelectSort(int* a, int n)
{int left 0, right n - 1;while (left right){int mini left, maxi left;for (int i left 1; i right; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[left], a[mini]);// 如果left和maxi重叠交换后修正一下if (left maxi){maxi mini;}Swap(a[right], a[maxi]);left;--right;}
}堆排序 就是以层序的方式从下往上从大到小的排。升序建大堆降序建小堆。 // 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){// 选出左右孩子中大的那一个if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}// 自己先实现 -- O(N*logN)int end n - 1;while (end 0){Swap(a[end], a[0]);AdjustDown(a, end, 0);--end;}
} 冒泡排序 冒泡排序好理解教学意义重大。简单的来说就是从一端开始两两交换把小的换在前面去就OK了 void BubbleSort(int* a, int n)
{for (int j 0; j n; j){bool exchange false;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange true;}}if (exchange false){break;}}
} 快速排序(快排 快排有很多种方法比如hoare法挖坑法前后指针法 1.hoare法 无言如图所示 int GetMidNumi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
int PartSort1(int* a, int left, int right)
{// 三数取中int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[midi], 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[keyi], a[left]);keyi left;return keyi;
} 挖坑法 int GetMidNumi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
int PartSort2(int* a, int left, int right)
{// 三数取中int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[midi], a[left]);// 21:10继续int key a[left];int hole left;while (left right){// 右边找小while (left right a[right] key)--right;a[hole] a[right];hole right;// 左边找大while (left right a[left] key)left;a[hole] a[left];hole left;}a[hole] key;return hole;
} 前后指针法 int GetMidNumi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
int PartSort3(int* a, int left, int right)
{// 三数取中int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[midi], a[left]);int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
} 归并排序递归 int GetMidNumi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}
int PartSort3(int* a, int left, int right)
{// 三数取中int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[midi], a[left]);int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi PartSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
} 总结 疯了疯了怎么才能讲清楚啊白话文一大堆还是图来说清楚没看清楚的啾咪留言喵喵鸭你的明白就是我的成长酸Q喵。 宝子你不点个赞吗不评个论吗不收个藏吗 最后的最后关注我关注我关注我你会看到更多有趣的博客哦 喵喵喵你对我真的很重要。
