营销网站建设教程,import wordpress,用wordpress怎么生成pdf_word_图片文件,做违法网站1.排序的概念及应用
1.1概念
排序:所谓排序#xff0c;就是一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。
1.2运用
购物筛选排序#xff1a; 1.3常见排序算法
2.实现常见的排序算法 int a[ {5,3,9,6,2,4,7,1,8}; 2…1.排序的概念及应用
1.1概念
排序:所谓排序就是一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
1.2运用
购物筛选排序 1.3常见排序算法
2.实现常见的排序算法 int a[ {5,3,9,6,2,4,7,1,8}; 2.1插入排序
基本思想直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其相关键码值逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。我们可以理解成玩扑克牌
2.1.1直接插入排序
当插入第i个元素时前面的arr[0],arr[1],arr[2].....,arr[i-1]已经排好序此时用arr[i]的排序码与arr[i-1],arr[i-2]....的排序码顺序相比较找到插入位置即将arr[i]插入原来位置上的与元素挨个向后移动。
代码实现:
void InsertSort(int* arr, int n)
{for (int i 0; i n-1; i){int end i;int tmp arr[end 1];while (end0){if (arr[end] tmp) {arr[end 1] arr[end];end--;}else{break;}}arr[end1] tmp;}
} 直接插入排序的特性总结 1.元素集合越接近有序直接插入排序算法的效率越高 2.时间复杂度O(N^2) 3.空间复杂度O(1) 2.1.2希尔排序 希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是先选定⼀个整数通常是gap n/31把 待排序⽂件所有记录分成各组所有的距离相等的记录分在同⼀组内并对每⼀组内的记录进⾏排 序然后gapgap/31得到下⼀个整数再将数组分成各组进⾏插⼊排序当gap1时就相当于 直接插⼊排序。它是在直接插⼊排序算法的基础上进⾏改进⽽来的综合来说它的效率肯定是要⾼于直接插⼊排序算 法的。 希尔排序的特性总结 1.希尔排序是对直接插入排序的优化 2.当gap1时都是预排序目的时让数组更接近有序。当gap1时数组已经接近有序的了这样就会很快。这样总体而言可以达到优化的效果。 代码实现:
/希尔排序
void shellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 31;//3 1 0 要保证最后一次为1for (int i 0; i n - gap; i){int end i;//n-gap-1int tmp arr[end gap];//n-1while (end0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
} 2.1.2.1希尔排序的时间复杂度计算
希尔排序的时间复杂度估算
外层循环外层循环的时间复杂度可以直接给出为O(log2 n) 或者 O(log3 n) 即 O(log n)
内层循环
假设一共有n个数据合计gap组则每组为n/gap个数据在每组中插入移动的次数最坏的情况下为1234.....(n/gap-1),一共是gap组因此
总计最坏情况下移动总数为gap*[123...n/gap-1]
gap取值有以除3为例n/3 n/9 n/27.....2 1 • 当gap为n/3时移动总数为n/3 ∗ (1 2) n • 当gap为n/9时移动总数为 n/9 ∗ (1 2 3 .... 8) n/9∗ 8(1 8)/2 4n • 最后⼀躺gap1即直接插⼊排序内层循环排序消耗为n 2.2选择排序
选择排序的基本思想每一次从待排序的数据元素中选出最小或者最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。
2.2.1直接选择排序
1.在元素集合arr[i]--arr[n-1]中选择最大和最小的数据元素
2.若它不是这个组元素中的最后一个元素或者第一个元素则将它与这组元素中的最后一个和第一个元素进行交换
3.在剩余的arr[i]--arr[n-1] arr[i1]--arr[n-2]集合中重复上面的步骤直到集合只剩一个元素 //选择排序
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (beginend){int mini begin;int maxi begin;for (int i begin; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}if (maxi begin){maxi mini;}Swap(arr[begin], arr[mini]);Swap(arr[end], arr[maxi]);begin;end--;}}
直接选择排序非常好理解但是效率不高实际中很少用
时间复杂度:O(N^2)
空间复杂度:O(1)
2.2堆排序 堆排序(Heapsort)是指利⽤堆积树堆这种数据结构所设计的⼀种排序算法它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆排降序建⼩堆。 void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}// 堆排序
void AdjustDwon(int* arr, int parent, int n)
{int child 2 * parent 1;//左孩子//大堆找最大//小堆找最小while (child n){if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child 2 * parent 1;}else{break;}}
}void HeapSort(int* arr, int n)
{//1.先建堆//升序建大堆//降序建小堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDwon(arr, i, n);}//交换根结点和最后一个有效数据的位置没交换一次少一个数据然后向下调整int end n - 1;while (end 0){Swap(arr[0], arr[end]);//向下调整AdjustDwon(arr, 0, end);end--;}
}2.3交换排序
交换排序基本思想 所谓交换就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较⼤的记录向序列的尾部移动键值较⼩的记录向序列的前部移动 2.3.1冒泡排序
前⾯在算法题中我们已经接触过冒泡排序的思路了冒泡排序是⼀种最基础的交换排序之所以叫做冒泡排序因为每⼀个元素都可以像⼩⽓泡⼀样根据⾃⾝⼤⼩⼀点⼀点向数组的⼀侧移动。 //冒泡排序
//时间复杂度0(N^2)
void BubbleSort(int* arr, int n)
{for (int i 0; i n; i){int exchange 0;for (int j 0; j n - i - 1; j){//升序if (arr[j] arr[j 1]){exchange 1;Swap(arr[j], arr[j 1]);}}if (exchange 0){break;}}
}
冒泡排序的特性总结
时间复杂度为O(N^2)
空间复杂度为O(1)
2.3.2快速排序
快速排序是一种高效的排序算法由英国计算机科学家托尼·霍尔Tony Hoare在1960年提出。它的基本思想是分而治之通过一趟排序将待排记录分割成独立的两部分其中一部分的所有记录均比另一部分的所有记录要小然后再按此方法对这两部分分别进行快速排序整个排序过程可以递归进行以至整个数据变成有序序列。
快速排序实现的主框架
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left right){return;}//找基准值midint key _QuickSort(arr, left, right);//左子序列[left,mid-1]QuickSort(arr, left, key - 1);//右子序列:[mid1,right]QuickSort(arr, key 1, right);
}
将区间中的元素划分的 _QuickSort方法主要有一下几种实现方式:
2.3.2.1hoare版本
算法思路
1.创建左右指针确定基准值
2.从右向左找比基准值小的数据从左向右找比基准值大的数据左右指针数据交换进入下次循环。当leftright时即right走到left的左侧而left扫描过的数据均不大于key因此right此时指向的数据一定不大于key。 left和right指向的数据与key相等时也要交换相等的值参与交换确实有一些损耗。实际还有各种复杂的场景假设数组中的数据大量重复时无法进行有效的数据分割。 代码实现
//hoare法
int _QuickSort(int* arr, int left, int right)
{int key left;left;while (leftright)//使效率更高{//right从右到左找比基准值小的while (leftrightarr[right]arr[key]){right--;}//left从左到右找比基准值大的while (leftrightarr[left]arr[key]){left;}if (left right){Swap(arr[left], arr[right--]);}}//跳出循环交换right和基准值Swap(arr[key], arr[right]);//返回基准值return right;
}
2.3.2.2挖坑法 思路创建左右指针。⾸先从右向左找出⽐基准⼩的数据找到后⽴即放⼊左边坑中当前位置变为新的坑然后从左向右找出⽐基准⼤的数据找到后⽴即放⼊右边坑中当前位置变为新的坑结束循环后将最开始存储的分界值放⼊当前的坑中返回当前坑下标即分界值下标 //挖坑法
int _QuickSort1(int* arr, int left, int right)
{int mid arr[left];int hole left;int key arr[hole];while (leftright){while (left right arr[right] key){right--;}//填坑arr[hole] arr[right];hole right;while (leftrightarr[left]key){left;}//填坑arr[hole] arr[left];hole left;}arr[hole] key;//返回基准值return hole;
} 2.3.2.3lomuto前后指针 创建前后指针从左往右找比基准值小的进行交换使得小的都排在基准值的左边。 //lomuto法
int _QuickSort2(int* arr, int left, int right)
{int prev left;int cur left 1;int key left;while (curright){if (arr[cur] arr[key] prev ! cur){Swap(arr[cur], arr[prev]);}cur;}Swap(arr[key], arr[prev]);//返回基准值return prev;
}
快速排序的特性
时间复杂度O(n*logn)
空间复杂度O(logn)
2.3.2.4非递归版本
非递归版本的快速排序需要借助数据结构栈
//非递归
//栈结构
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInite(st);//入栈STPush(st, right);STPush(st, left);while (!STEmpty(st)) {//取栈顶--取两次int begin STTop(st);STPop(st);int end STTop(st);STPop(st);//找基准值int prev begin;int cur begin 1;int key begin;while (curend){if (arr[cur] arr[key] prev ! cur){Swap(arr[prev], arr[cur]);}cur;}Swap(arr[prev], arr[key]);key prev;//根据基准值划分左右区间//left:[begin,key-1]//right:[key1,end]if (key1end){STPush(st, end);STPush(st, key 1);}if (beginkey-1){STPush(st, key - 1);STPush(st, begin);}}STDestroy(st);
}
2.4归并排序 归并排序算法思想归并排序MERGE-SORT是建⽴在归并操作上的⼀种有效的排序算法,算法是采⽤分治法Divide and Conquer的⼀个⾮常典型的应⽤。将已有序的⼦序列合并得到完全有序的序列即先使每个 ⼦序列有序再使⼦序列段间有序若将两个有序表合并成⼀个有序表称为⼆路归并。归并排序核⼼步骤
void _mergeSort(int* arr, int left, int right,int* tmp)
{if (left right){return;}int mid (left right) / 2;//[left,mid] [mid1,right]_mergeSort(arr, left, mid, tmp);_mergeSort(arr, mid 1, right, tmp);//合并//[left,mid] [mid1,right]int begin1 left;int end1 mid;int begin2 mid 1;int end2 right;int index begin1;while (begin1end1begin2end2){if (arr[begin1] arr[begin2]){tmp[index] arr[begin1];}else{tmp[index] arr[begin2];}}//要么begin1越界要么begin2越界while (begin1end1){tmp[index] arr[begin1];}while (begin2end2){tmp[index] arr[begin2];}//把tmp中的数据拷贝会arr中for (int i left; i right; i){arr[i] tmp[i];}
}
//归并排序
void mergeSort(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);_mergeSort(arr, 0, n - 1, tmp);free(tmp);
}
归并排序特性总结
时间复杂度O(n*logn)
空间复杂度 O(n)
2.5计数排序 计数排序⼜称为鸽巢原理是对哈希直接定址法的变形应⽤。 操作步骤 1统计相同元素出现次数 2根据统计的结果将序列回收到原来的序列中 //计数排序
void CountSort(int* arr, int n)
{int max arr[0];int min arr[0];//找到最大值和最小值求范围for (int i 1; i n; i){if (arr[i] min){min arr[i];}if (arr[i] max){max arr[i];}}int range max - min 1;//开辟数组大小int* count (int*)malloc(sizeof(int) * range);if (count NULL){perror(malloc fail!);exit(1);}//初始化置为0memset(count, 0, range * sizeof(int));//统计数组中每个数据出现的次数for (int i 0; i n; i){count[arr[i] - min];}//取count中的数据往arr中放int index 0;for (int i 0; i range; i){while (count[i]--){arr[index] i min;}}
}2.6测试代码排序性能对比
//测试排序性能
void Testop()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);int* a8 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];a8[i] a1[i];}int begin7 clock();BubbleSort(a7, N);int end7 clock();int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();shellSort(a2, N);int end2 clock();int begin3 clock();SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();QuickSort(a5, 0, N - 1);//QuickSortNonR(a5, 0, N - 1);int end5 clock();int begin6 clock();mergeSort(a6, N);int end6 clock();int begin8 clock();CountSort(a8, N);int end8 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);printf(BubbleSort:%d\n, end7 - begin7);printf(CountSort:%d\n, end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}
