做网站的代码有哪些,wordpress文章列表不显示,html简单代码模板,网站建设入什么会计科目本文中的Swap()函数都是下面这段代码 // 交换
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}文章目录 常见排序#xff1a;一.插入排序1.直接插入排序#xff1a;2.希尔排序#xff1a; 二.选择排序1.选择排序#xff1a;2.堆排序#xff1a; 三.交换排… 本文中的Swap()函数都是下面这段代码 // 交换
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
} 文章目录 常见排序一.插入排序1.直接插入排序2.希尔排序 二.选择排序1.选择排序2.堆排序 三.交换排序1.冒泡排序2.快速排序注重要三数取中1Hoare法2挖坑法3前后指针法快速排序递归版快速排序非递归版 四.归并排序1.归并排序归并排序递归版归并排序非递归版 五.计数排序 常见排序 一.插入排序
1.直接插入排序 直接插入排序的基本思想通过取一个数a与前面的数比较a小则将前面的数后移a继续向前比较直到找到比a更小的数插入到该位置。
代码实现
// 直接插入排序 时间O(N^2) 空间O(1)
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];// [0,end]区间为有序的排序好的有序区间// end1位置的值插入到有序区间中while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}2.希尔排序 希尔排序的基本思想先选定一个整数gap将需要排序的内容分为gap组所有的距离为gap的在同一组并对每一组内的数进行排序。然后重复上述操作直到gap减为1。
我们来看一下分步图
// 希尔排序 时间O(N^1.3)大致 空间O(1)
void ShellSort(int* a, int n)
{int gap n;while (gap 1){// 1保证最后一个gap一定是1// gap 1 时是预排序// gap 1 时是插入排序gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}希尔排序就是对直接插入排序的优化当gap 1时都是在对数组进行预排序当gap 1时此时的数组已经接近有序了且当gap为1时我们代入到希尔排序的代码中再与上面的插入排序比较一下我们就能发现是一样的。
二.选择排序
1.选择排序 选择排序的基本思想每一次从待排序的数据中选出最小或最大值将其放在前面直到全部待排序的数据元素排完。
为了提高排序效率我们也可以同时选出最小值和最大值将最小值放在前面最大值放在后面。
// 选择排序 时间O(N^2) 空间O(1)
void SelectSort(int* a, int n)
{int begin 0, end n - 1; // 定义首位元素地址,同时找到最大和最小的分别放到首和尾while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i) // 找到最大和最小值的下标{if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);// 若首元素最大将最小值交换到最前面后begin会与maxi重叠// 需要更新maxi防止begin与maxi重叠后将把最小值交换到最后if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
}2.堆排序 堆排序需要我们对堆这个数据结构有一定了解。 堆排序时利用数据结构树堆进行排序的一种算法。通过堆进行选择数据。排升序建大堆排降序建小堆。
我们来看一下分步图 // 堆排序 时间O(NlogN) 空间O(1)
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){//找到两个孩子中较小/较大 的孩子 if (a[child 1] a[child] child 1 n){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);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
三.交换排序
1.冒泡排序 冒泡排序的基本思路从前向后两两比较小的放前大的放后
// 冒泡排序 时间O(N^2) 空间O(1)
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){int flag 1; // 标记设为1若后面都有序则直接进行下一次循环for (int j 0; j n - i; j){if (a[j - 1] a[j]){Swap(a[j - 1], a[j]);flag 0;}}if (flag 1){break;}}
}2.快速排序 快排的代码我们采用分离处理下面三种方法的代码只写明单趟排序。递归的部分在三种方法之后。 快速排序的基本思想任取待排序元素中的某个元素作为基准值key以这个基准值key将数组分割为两部分左边的所有元素均小于基准值key右边的所有元素均大于基准值key然后将左边重复该过程右边重复该过程直到数组有序。
注重要三数取中
在选取基准值key的时候如果数组本身是有序的直接对左边或者右边取key这时算法的时间复杂度就会退化O(N^2)因此递归的深度比较大可能会导致栈溢出这就很坑。所以我们应该科学的选key这种方法就是三数取中。
三数取中的基本思路我们取最左边中间最右边三个值对这三个值进行比较选择中间大小的值作为key。
// 三数取中
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;// left midi rightif (a[left] a[midi]){if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return right;}else{return left;}}else // a[left] a[midi]{if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return left;}else{return right;}}
}1Hoare法 在用Hoare法进行排序时需要注意key的位置左边做key右边先走右边做key左边先走这样才能保证相遇位置比key小。 我们来看一下分步图
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]); // 将key值放在左边int keyi left;int begin left, end right;while (begin end){// 右边找小右边先走while (begin end a[keyi] a[end]){end--;}// 左边找大while (begin end a[keyi] a[begin]){begin;}Swap(a[begin], a[end]);}Swap(a[keyi], a[begin]);return begin;
}2挖坑法 挖坑法的基本思路先用key存储基准值将第一个位置形成一个坑位右侧找比key小的数放入坑位这个数的原位置形成新的坑位重复这个操作直到最后的坑位左侧都小于key右侧都大于key。
注意当此处为坑位时不进行移动移动另一个指针。
我们来看一下分步图
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int key a[left];int begin left, end right;int holi left;while (begin end){while (begin end key a[end]){end--;}a[holi] a[end];holi end;while (begin end key a[begin]){begin;}a[holi] a[begin];holi begin;}a[begin] key;return begin;
}3前后指针法 前后指针法基本思路cur找比key小的数prev找比key大的数然后进行交换cur越界最后将key和prev交换。
这种方法也不用和Hoare法一样考虑先走左还是先走右也更易理解。
我们来看一下分步图
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;int prev left;int cur prev 1;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[keyi], a[prev]);return prev;
}快速排序递归版
对上面三种方法进行递归进行多次排序。
void QuickSort(int* a, int left, int right)
{if (left right)return;if ((right - left 1) 10) // 这里小优化一下数据内容小于10个的时候直接进行插入排序不走递归{InsertSort(a left, right - left 1);}else{// 三种方式随意选int keyi PartSort1(a, left, right);//int keyi PartSort2(a, left, right);//int keyi PartSort3(a, left, right);// [left, keyi-1] keyi [keyi1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}
}快速排序非递归版 快排的非递归实现需要用到栈这个数据结构因此需要先了解栈。 快排的非递归基本思路用栈模拟递归的实现在栈中存储区域范围然后取栈顶区间单趟排序右左子区间入栈循环上面的操作直到栈为空。 // 快速排序 非递归实现
#includeStack.h
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(st);StackPush(st, right); // 先存right才能后用StackPush(st, left); // 后存left才能先用while (!StackEmpty(st)) // 循环每走一次相当于之前的一次递归{int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);int keyi PartSort1(a, begin, end); // 三种方式随意选// [begin, keyi-1] keyi [keyi1, end]if (keyi 1 end){StackPush(st, end);StackPush(st, keyi 1);}if (begin keyi - 1){StackPush(st, keyi - 1);StackPush(st, begin);}}StackDestroy(st);
}四.归并排序
1.归并排序 归并算法的基本思路将已经有序的子序列合并得到完全有序的序列即先把每个子序列变成有序然后两个子序列有序的合并成为一个新的有序子序列最终合并为一个完整的有序序列。
我们来看一下分步图
归并排序递归版
// 归并排序 时间O(NlogN) 空间O(N)
//
// 归并排序递归实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin end){return;}int midi (begin end) / 2; // [begin, midi] [midi 1, end] 分为两个区间// 递归_MergeSort(a, tmp, begin, midi);_MergeSort(a, tmp, midi 1, end);int begin1 begin, end1 midi;int begin2 midi 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp NULL;
}归并排序非递归版
归并排序的基本思路首先设置gap表示归并的元素个数然后对子序列中的gap个元素进行归并更新gap重复上面操作以循环的形式模拟递归的过程。
我们来看一下分步图
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);}int gap 1; // 每组归并的数据个数while (gap n){for (int i 0; i n; i 2 * gap) // i表示每组归并的起始位置{// [begin1, end1][begin2, end2]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;int j i;// 这里需要对范围进行修正否则有可能会导致数组越界访问// 第二组越界整组都不需要归并if (begin2 n){break;}// 第二组的尾end2越界修正后再归并if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);tmp NULL;
}五.计数排序 计数排序的基本思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。首先定义一个数组用来统计每个数出现的次数然后根据统计的结果将序列回收到原来的序列中。
// 计数排序
void CountSort(int* a, int n)
{// 找最大最小值max - min 1为count数组的长度节省空间int min a[0], max a[0];for (int i 1; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* count (int*)calloc(range, sizeof(int));if (count NULL){perror(malloc fail);}// 统计次数for(int i 0; i n; i){count[a[i] - min];}// 排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min; // 前面存储数据的时候减去了min这里需要还原加上min}}free(count);count NULL;
}
