制作网站 公司简介,大型做网站的公司,ui设计经典案例,电子商务网站推广案例C 数据结构算法 学习笔记(32) -五大排序算法
选择算法
如下若有多个女生的身高需要做排序: 常规思维:
第一步先找出所有候选美女中身高最高的#xff0c;与最后一个数交换 第二步再找出除最后一位美女外其它美女中的最高者#xff0c;与倒数第二个美女交换位置 再找出除最…C 数据结构算法 学习笔记(32) -五大排序算法
选择算法
如下若有多个女生的身高需要做排序: 常规思维:
第一步先找出所有候选美女中身高最高的与最后一个数交换 第二步再找出除最后一位美女外其它美女中的最高者与倒数第二个美女交换位置 再找出除最后两位美女外其它美女中的最高者与倒数第三个美女交换位置因为倒数 第三个本身已是最大的所以实际无需交换. 重复以上步骤直到最后只剩下一人此时所有的美女均已按照身高由矮到高的 顺序排列 代码实现:
#includestdio.h
#includestdlib.h
void swap(int* num1, int* num2)//交换两个变量的值
{int temp *num1;*num1 *num2;*num2 temp;
}void SelectSort1(int arr[], int len) {for (int i 0; i len - 1; i) {int max 0;for (int j 1; j len - i; j) { //查找未排序的元素if (arr[j] arr[max]) { //找到目前最小值max j;}}//printf(max:%dbeauties%d\n,max,len-i-1);if (max ! (len - i - 1)) {swap(arr[max], arr[len - i - 1]);}}
}
void SelectSort2(int arr[], int len) {int i, j;for (i 0; i len - 1; i){int min i;for (j i 1; j len; j) { //查找未排序的元素if (arr[j] arr[min]) { //找到目前最小值min j; //记录最小值}}swap(arr[min], arr[i]); //交换}
}
int main(void) {int beauties[] { 163,161,158,165,171,170,163,159,162 };int len sizeof(beauties) / sizeof(beauties[0]);SelectSort2(beauties, len);for (int i 0; i len; i) {printf(%d , beauties[i]);}system(pause);
}冒泡算法
当我们采用前面的选择排序时我们仍然要将候选者遍历5遍才能完成最终的排序但其 实本身这些美女出了第一个外已经很有序了我们只需要把第一个和第二个交换然后又和 第三个交换如此循环直到和最后一个交换后整个数组基本就有序了 当然并不是每次都这么幸运像下面的情况就会更复杂一些一趟并不能完全解决问题 我们需要多趟才能解决问题. 经过上述五步后,得到的结果: 此时,我们只保障了最后一个数是最大的,并不能保障前面的数一定会有序,所以,我们继续按 照上面五步对剩下的5个数继续进行一次排序,数组就变得有序了. 以上过程就是冒泡排序:通过重复地遍历未排序的数列一次比较两个元素如果它们的顺 序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列 已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢得像泡泡一样“浮”到数 列的顶端,故而得名
代码实现:
#include iostream
#include stringusing namespace std;void swap(int* tmp1, int* tmp2)
{int tmp3 *tmp1;*tmp1 *tmp2;*tmp2 tmp3;
}int main()
{int height2[] { 156,162,161,172,167,169,155 };int height[] { 155,158,161,163,172,174 };int size sizeof(height) / sizeof(height[0]);for (int i 0; i size-1; i){bool sorted true;for (int j 0; j size-i-1; j){if (height[j] height[j1]){ sorted false;swap(height[j], height[j 1]);}}if (sorted true) break;}for (int i 0; i size; i){cout height[i] ;}system(pause);return 0;
}插入排序 首先,我们只考虑第一个元素,从第一个元素171开始该元素可以认为已经被排序 取下一个元素161并记录并让161所在位置空出来,在已经排序的元素序列中从后向前扫 描 该元素171大于新元素将该元素移到下一位置 171前已经没有最大的元素了,则将161插入到空出的位置 取下一个元素163并让163所在位置空出来,在已经排序的元素序列中从后向前扫描 该元素171大于新元素163将该元素移到下一位置 继续取171前的元素新元素比较,直到找到已排序的元素小于或者等于新元素的位置新 元素大于161,则直接插入空位中 重复步骤2~7直到完成排序
插入排序:它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描 找到相应位置并插入。插入排序在实现上通常采用in-place排序即只需用到O(1)的额外空间 的排序因而在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供 插入空间。
具体算法描述如下 从第一个元素开始该元素可以认为已经被排序 取出下一个元素在已经排序的元素序列中从后向前扫描 如果该元素已排序大于新元素将该元素移到下一位置 重复步骤3直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置 重复步骤2~5
代码实现::
#include iostream
#include stringusing namespace std;void InsertSort(int* height, int size)
{int current 0;int preIndex 0;for (int i 1; i size; i){current height[i];preIndex i-1;while (preIndex 0 height[preIndex] current){height[preIndex 1] height[preIndex];preIndex--;}height[preIndex 1] current;}
}int main()
{int height[] { 152,163,161,159,172,170,168,151 };int size (sizeof(height) / sizeof(height[0]));InsertSort(height, size);cout The sorting result is endl;for (int i 0; i size; i){cout height[i] ;}system(pause);return 0;
}希尔排序
插入排序虽好,但是某些特殊情况也有很多缺点,比如像下面这种情况 169前的元素基本不用插入操作就已经有序,元素1和2的排序几乎要移动数组前面的所有 元素!!!于是,有个老帅哥就提出了优化此问题的希尔排序!
希尔排序是希尔Donald Shell于1959年提出的一种排序算法。希尔排序也是一种插入排 序它是简单插入排序经过改进之后的一个更高效的版本也称为缩小增量排序。它与插入排序 的不同之处在于它会优先比较距离较远的元素。
希尔排序是把记录按下表的一定增量分组对每组使用直接插入排序算法排序随着增量逐 渐减少每组包含的元素越来越多当增量减至1时所有元素被分成一组,实际上等同于执行一 次上面讲过的插入排序算法便终止。
希尔排序的基本步骤
选择增量gaplength/2缩小增量gapgap/2
增量序列用序列表示增量选择{n/2,(n/2)/2,…,1}
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序具体算法描述
选择一个增量序列t1t2…tk其中titjtk1
按增量序列个数k对序列进行k趟排序
每趟排序根据对应的增量ti将待排序列分割成若干长度为m的子序列分别对各子表进 行直接插入排序;
仅增量因子为1时整个序列作为一个表来处理表长度即为整个序列的长度。 #include iostream
#include string
using namespace std;void InsertSort(int arr[], int len)
{int gap len / 2;for (; gap 0; gap gap / 2) {for (int i gap; i len; i) {int current arr[i];int j 0;for (j i - gap; j 0 arr[j] current; j - gap) {arr[j gap] arr[j];}arr[j gap] current;}}
}int main()
{int height[] { 152,163,161,159,172,170,168,151 };int size (sizeof(height) / sizeof(height[0]));InsertSort(height, size);cout The sorting result is endl;for (int i 0; i size; i){cout height[i] ;}system(pause);return 0;
}归并排序
当两个组数据已经有序我们可以通过如下方式以下简称归并大法让两组数据快速有序 我们可以依次从两组中取最前面的那个最小元素依次有序放到新的数组中然后再把新数组 中有序的数据拷贝到原数组中快速完成排序
具体步骤:
对于下面这一组待排序的数组 先以中间为界把其均分为A和B两个数组如果是奇数个允许两组数相差一个 如果A和B两组数据能够有序则我们可以通过上面的方式让数组快速排好序。 此时A组有4个成员B组有5个成员,但两个数组都无序然后我们可以采用分治法继 续对A组和B组进行均分以A组为例又可以均分A1和A2两个组如下 均分后A1组和A2组仍然无序继续利用分治法细分以A1组为例A1又可分成如下 两组 数组细分到一个元素后这时候我们就可以采用归并法借助一个临时数组将数组A1有序化 A2同理 依次类推将A1组和A2组归并成有序的A组B组同理 最后将A和B组使用归并大法合并就得到了完整的有序的结果 代码实现:
#include iostream
#include stringusing namespace std;//void mergeAdd_demo(int arr[], int left, int mid, int right)
//{
// int temp[64] { 0 };
// int i left;
// int j mid;
// int k 0;
//
// while (i mid j right)
// {
// if (arr[i] arr[j])
// {
// temp[k] arr[i];
// }
// else
// {
// temp[k] arr[j];
// }
// }
// while (i mid)
// {
// temp[k] arr[i];
// }
//
// while (j right)
// {
// temp[k] arr[j];
// }
//
// memcpy(arr left, temp, sizeof(int) * (right - left 1));
//}void mergeAdd(int arr[], int left, int mid, int right, int* temp)
{//int temp[64] { 0 };int i left;int j mid;int k left;while (i mid j right){if (arr[i] arr[j]){temp[k] arr[i];}else{temp[k] arr[j];}}while (i mid){temp[k] arr[i];}while (j right){temp[k] arr[j];}memcpy(arr left, temp left, sizeof(int) * (right - left 1));
}void mergeSort(int arr[], int left, int right, int* temp)
{int mid 0;if (left right){mid left(right-left)/2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid 1, right, temp);mergeAdd(arr, left, mid1, right, temp);}
}int main()
{int height[] { 10,11,12,13,2,4,5,8 };int len sizeof(height) / sizeof(height[0]);int* temp new int[len];//int mid len / 2;mergeSort(height, 0, len - 1, temp);//mergeAdd(height, 0, mid, len - 1,temp);for (int i 0; i len; i){cout height[i] ;}system(pause);return 0;
}快速排序
具体做法为:
每次选取第一个数为基准数然后使用“乾坤挪移大法”将大于和小于基准的元素分别放置于基准数两边继续分别对基准数两侧未排序的数据使用分治法进行细分处理直至整个序列有序。
对于下面待排序的数组: 代码实现:
#include iostream
#include stringusing namespace std;
int partition(int arr[], int low, int high)
{int i low;int j high;int base arr[low];if (low high){while (i j){while (i j arr[j] base){j--;}if (i j){arr[i] arr[j];}while (i j arr[i] base){i;}if (i j){arr[j--] arr[i];}}arr[i] base;}return i;
}void QuickSort(int* arr, int low, int high)
{if (low high){int index partition(arr, low, high);QuickSort(arr, low, index - 1);QuickSort(arr, index 1, high);}
}int main()
{int arr[] { 163,161,158,165,171,170,163,159,162 };int len sizeof(arr) / sizeof(arr[0]);//int index partition(arr, 0, len - 1);QuickSort(arr, 0, len - 1);cout Executing the Quick Sort, result as endl;for (int i 0; i len; i){cout arr[i] ;}system(pause);return 0;
}各大算法对比图
