村建站全称,做网站 技术,网络营销计划书怎么写,抚州做网站公司一、冒泡排序
冒泡排序#xff08;Bubble Sort#xff09;#xff0c;顾名思义#xff0c;就是指越小的元素会经由交换慢慢“浮”到数列的顶端。
算法原理
从左到右#xff0c;依次比较相邻的元素大小#xff0c;更大的元素交换到右边#xff1b;从第一组相邻元素比较…一、冒泡排序
冒泡排序Bubble Sort顾名思义就是指越小的元素会经由交换慢慢“浮”到数列的顶端。
算法原理
从左到右依次比较相邻的元素大小更大的元素交换到右边从第一组相邻元素比较到最后一组相邻元素这一步结束最后一个元素必然是参与比较的元素中最大的元素按照大的居右原则重新从左到后比较前一轮中得到的最后一个元素不参4与比较得出新一轮的最大元素按照上述规则每一轮结束会减少一个元素参与比较直到没有任何一组元素需要比较。
代码实现
// 冒泡排序
void BubbleSort(int* arr, int n)
{int i 0;for (i 0; i n - 1; i) // 冒泡排序趟数{int j 0;int flag 1;for (j 0; j n - i - 1; j) // 待排序区间进行比较交换{if (arr[j] arr[j 1]){int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;flag 0;}}if (flag 1){// 说明已经有序break;}}
}拓展 O()
二、快速排序
快速排序Quick Sort是冒泡排序的改进版之所以“快速”是因为使用了分治法。它也属于交换排序通过元素之间的位置交换来达到排序的目的。
算法原理
在序列中随机挑选一个元素作基准将小于基准的元素放在基准之前大于基准的元素放在基准之后再分别对小数区与大数区进行排序。
一趟快速排序的具体做法是
设两个指针 i 和 j分别指向序列的头部和尾部先从 j 所指的位置向前搜索找到第一个比基准小的值把它与基准交换位置再从 i 所指的位置向后搜索找到第一个比基准大的值把它与基准交换位置重复 2、3 两步直到 i j。
仔细研究一下上述算法我们会发现在排序过程中对基准的移动其实是多余的因为只有一趟排序结束时也就是 i j 的位置才是基准的最终位置。
由此可以优化一下算法
设两个指针 i 和 j分别指向序列的头部和尾部先从 j 所指的位置向前搜索找到第一个比基准小的数值后停下来再从 i 所指的位置向后搜索找到第一个比基准大的数值后停下来把 i 和 j 指向的两个值交换位置重复步骤 2直到 i j最后将相遇点指向的值与基准交换位置。 代码
void QuickSort(int array[], int low, int high) {int i low; int j high;if(i j) {return;}int temp array[low];while(i ! j) {while(array[j] temp i j) {j--;}while(array[i] temp i j) {i;}if(i j) {swap(array[i], array[j]);}}//将基准temp放于自己的位置第i个位置swap(array[low], array[i]);QuickSort(array, low, i - 1);QuickSort(array, i 1, high);
}
三、插入排序
直接插入排序Straight Insertion Sort是一种简单直观的排序算法它的基本操作是不断地将尚未排好序的数插入到已经排好序的部分好比打扑克牌时一张张抓牌的动作。在冒泡排序中经过每一轮的排序处理后序列后端的数是排好序的而对于插入排序来说经过每一轮的排序处理后序列前端的数都是排好序的。
算法原理
先将第一个元素视为一个有序子序列然后从第二个元素起逐个进行插入直至整个序列变成元素非递减有序序列为止。如果待插入的元素与有序序列中的某个元素相等则将待插入元素插入大相等元素的后面。整个排序过程进行 n-1 趟插入
代码
//写法1
void insert_sort(int *arr, int len){int i, j;for (i 1; i len; i){int tmp arr[i];//待插入数for (j i; j 0 arr[j - 1] tmp; j--){arr[j] arr[j - 1];//大的数依次右移}arr[j] tmp;}
}//写法2
void insert_sort_1(int *arr, int n)
{int i 0, j 0;for (i 1; i n; i){j i;//一直拿当前数与前面数比有它的就停止没有接着交换位置并往前比while (j 1){if (arr[j] arr[j - 1]) {swap(arr, j, j - 1);}j--;}}
}四、希尔排序
希尔排序Shell’s Sort是第一个突破 O(n²) 的排序算法是直接插入排序的改进版又称“缩小增量排序”Diminishing Increment Sort。它与直接插入排序不同之处在于它会优先比较距离较远的元素。
算法原理
先将整个待排序列分割成若干个子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。
子序列的构成不是简单地“逐段分割”将相隔某个增量的记录组成一个子序列让增量逐趟缩短直到增量为 1 为止。 代码实现
这里的代码是通过一次就把所有元素排序完成。
gap的取值保证最后为1就可以了gap不等于1之前其实都是预排序让数据趋近于有序。
// 希尔排序
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1;//保证最后gap为1就可以了int i 0;for (i 0; i n - gap; i)//多组元素同时进行插入排序{int end i;int tmp arr[endgap];while (end 0){if (arr[end] tmp){arr[endgap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}
五、选择排序
每次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置直到全部待排序的元素排序完。
原理 每次从无序区间中选取一个最大(或最小)的一个元素存放在无序区间的最后(或最前)直到全部待排序的元素排序完。 在元素集合中a r r [ i ] a r r [ n − 1 ] arr[i]~arr[n-1]arr[i] arr[n−1]中选择最大(最小的元素) 若它不是这组元素中的最后一个(第一个元素)则将它与这组元素中的最后一个(第一个)元素交换 在剩余的a r r [ i ] a r r [ n − 2 ] arr[i]~arr[n-2]arr[i] arr[n−2]集合中重复此步骤直到集合中剩余一个元素为止 代码
// 选择排序
void SelectSort(int* arr, int n)
{int i 0;for (i 0; i n - 1; i){int minIndex i;//记录待排序区间最小元素下标int j 0;for (j i 1; j n; j){if (arr[minIndex] arr[j]){minIndex j;}}int tmp arr[minIndex];arr[minIndex] arr[i];arr[i] tmp;}
}
六、堆排序
堆排序是利用数据结构堆的特性来进行排序它也是一种选择排序它通过堆来选取数据。排升序建大堆排降序建小堆。 堆的详细介绍可以看这一篇文章数据结构堆的详解
原理 每次将堆顶元素和最后一个元素进行交换再进行向下调整然后缩小待排序区间直到数据有序因为堆顶的元素一定是一组数据中的最大或者最小值。
注意向下调整的前提是这个根节点的左右子树一定要是一个堆(大堆或小堆) 代码
void HeapAdjust(int* arr, int start, int end)
{int tmp arr[start];for (int i 2 * start 1; i end; i i * 2 1){if (i end arr[i] arr[i 1])//有右孩子并且左孩子小于右孩子{i;}//i一定是左右孩子的最大值if (arr[i] tmp){arr[start] arr[i];start i;}else{break;}}arr[start] tmp;
}
void HeapSort(int* arr, int len)
{//第一次建立大根堆从后往前依次调整for(int i(len-1-1)/2;i0;i--){HeapAdjust(arr, i, len - 1);}//每次将根和待排序的最后一次交换然后在调整int tmp;for (int i 0; i len - 1; i){tmp arr[0];arr[0] arr[len - 1-i];arr[len - 1 - i] tmp;HeapAdjust(arr, 0, len - 1-i- 1);}
}
int main()
{int arr[] { 9,5,6,3,5,3,1,0,96,66 };HeapSort(arr, sizeof(arr) / sizeof(arr[0]));printf(排序后为:);for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d , arr[i]);}return 0;
}