兼职做问卷调查的网站好,网站开发公司一站式服务,有没有好的网站可以学做头发,仁怀网站建设排序上
排序上
交换类排序
基本思想#xff1a;所谓交换#xff0c;就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置#xff0c;交换排序的特点是#xff1a;将键值较大的记录向序列的尾部移动#xff0c;键值较小的记录向序列的前部移动。
冒泡…排序上
排序上
交换类排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
冒泡排序 冒泡排序的特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
代码实现
void BublleSort(int*array, int size)
{for (int i 0; i size - 1; i) //总共冒泡的趟数{//冒泡的方式-----用相邻元素进行比较for (int j 0; j size - i - 1; j) //一次冒泡{if (array[j]array[j 1])Swap(array[j], array[j 1]);}}
}冒泡排序优化
void BublleSort(int*array, int size)
{ for (int i 0; i size - 1; i) //总共冒泡的趟数{int IsChange 0; //查看这一趟有没有交换//冒泡的方式-----用相邻元素进行比较for (int j 0; j size - i - 1; j) //一次冒泡{if (array[j]array[j 1]){Swap(array[j], array[j 1]);IsChange 1;} }if (!IsChange) //如果没有交换return;}
}快速排序
一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
快速排序的特性总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)最差场景单支树O(N2)空间复杂度O(logN)稳定性不稳定快排参考链接
代码实现
int Partion(int*array, int left, int right)
{//划分基准值
}
void QuickSort(int *array, int left, int right)
{if (right - left 1){int div Partion(array, left, right);QuickSort(array, left, div);QuickSort(array, div 1, right);}
}划分基准值的方式
hoare版本
int Partion(int*array, int left, int right)
{int key array[right - 1];int begin left;int end right - 1;while (beginend){//从前往后找比基准值大的元素找到就停下来,等于也往前走因为找的是大的while (begin endarray[begin] key)begin;//end从后往前找比基准值小的元素找到就停下来等于也往前走找的是小的不是等于while (begin endarray[end] key)end--;if (begin end)Swap(array[begin], array[end]);}if (begin ! right - 1)Swap(array[begin], array[right-1]);return begin;
}挖坑法
int Partion2(int*array, int left, int right)
{int key array[right - 1];int begin left;int end right - 1;while (beginend){while (beginendarray[begin] key)begin;if (beginend){//上一个坑是endbegin是比基准值大的数array[end] array[begin];end--;}while (beginendarray[end] key)end--;if (beginend){//上次坑是end填坑的是begin填完坑后begin成坑由新end比基准值小的数来填array[begin] array[end];begin;}}array[begin] key;return begin;
}前后指针版本
int Partion3(int*array, int left, int right)
{int key array[right - 1];int cur left;int pre cur - 1;while (curright){if (array[cur] key pre ! cur)Swap(array[cur], array[pre]);cur;}if (pre ! right - 1)Swap(array[pre], array[right - 1]);return pre;
}快排的优化
三数取中法选key递归到小的子区间时可以考虑使用插入排序
三数取中法
//三数取中法
int GetMiddleIdx(int*array, int left, int right)
{int mid left ((right - left) 1);//left mid right-1if (array[left] array[right - 1]){if (array[mid] array[left])return left;else if (array[mid]array[right - 1])return right - 1;elsereturn mid;}else{if (array[mid] array[left])return left;else if (array[mid] array[right - 1])return right - 1;elsereturn mid;}
}
int Partion(int*array, int left, int right)
{int middle GetMiddleIdx(array, left, right);if (middle ! right - 1)Swap(array[middle], array[right - 1]);int key array[right - 1];int begin left;int end right - 1;while (beginend){//从前往后找比基准值大的元素找到就停下来,等于也往前走因为找的是大的while (begin endarray[begin] key)begin;//end从后往前找比基准值小的元素找到就停下来等于也往前走找的是小的不是等于while (begin endarray[end] key)end--;if (begin end)Swap(array[begin], array[end]);}if (begin ! right - 1)Swap(array[begin], array[right - 1]);return begin;
}元素个数小用直接插入排序
void QuickSort(int *array, int left, int right)
{if (right - left 16)//如果快排的元素个数没有达到16及其以上就用插入排序InsertSort(array, right - left);else{int div Partion(array, left, right);QuickSort(array, left, div);QuickSort(array, div 1, right);}
}快速排序非递归写法
#includestack.h
//快排非递归
void QuickSortNor(int*array, int size)
{int left 0;int right size;Stack s;StackInit(s);StackPush(s,right);StackPush(s,left); //后进去的先出来先出来的是左while (!StackEmpty(s)){left StackTop(s);StackPop(s);right StackTop(s);StackPop(s);if (left right){int div Partion3(array, left, right);//先保存右半部分,先进后出来StackPush(s,right);//右半部分右边界StackPush(s, div 1);//右半部分左边界//再保存左边部分后进先出来StackPush(s, div);//左半部分右边界StackPush(s, left);//左半部分左边界}}StackDestroy(s);
}归并排序
归并排序
基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
代码实现
//归并到temp临时空间里
//两个有序序列合并成一个
void MergeData(int*array, int left, int mid, int right, int *temp)
{int begin1 left, end1 mid;int begin2 mid, end2 right;int index left;while (begin1 end1 begin2 end2)//第一个和第二个区间里的元素没有处理完{if (array[begin1] array[begin2])temp[index] array[begin1];elsetemp[index] array[begin2];}//如果第一个空间里的数没有搬移完while (begin1 end1)temp[index] array[begin1];//第一个空间搬移完了第二个空间里的元素没有搬移完while (begin2 end2)temp[index] array[begin2];
}
void _MergeSort(int*array, int left, int right,int*temp)
{//int*temp(int*)malloc(sizeof(array[left])*(right-left));if (right - left1) //区间里的元素超过一个再排序{//找中间位置int mid left ((right - left) 1);_MergeSort(array, left, mid,temp);_MergeSort(array, mid, right,temp);MergeData(array, left, mid, right, temp);memcpy(array left, temp left, sizeof(array[left])*(right - left));}
}
void MergeSort(int *array, int size)
{int *temp (int*)malloc(size*sizeof(array[0]));if (NULL temp){assert(0);return;}_MergeSort(array, 0, size, temp);free(temp);
}归并排序非递归
void MergeSortNor(int *array, int size)
{int *temp (int*)malloc(size*sizeof(array[0]));if (NULL temp){assert(0);return;}int gap 1;while (gap size){for (int i 0; i size; i 2 * gap){int left i;//左int mid left gap;//中int right mid gap;//右if (mid size)mid size;if (right size)right size;MergeData(array, left, mid, right, temp);}memcpy(array, temp, (sizeof(array[0])*size));gap * 2;}free(temp);
}非比较排序
思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 计数排序的特性总结
计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围)稳定性稳定
代码实现
//场景:数据密集集中在某个范围中
void CountSort(int*array, int size)
{int minVal array[0];//范围的左边界值int maxVal array[0];//范围的右边界值//1--找数据的范围for (int i 1; i size; i){if (array[i] minVal)minVal array[i];if (array[i]maxVal)maxVal array[i];}//2--计算保存计数的空间int range maxVal - minVal 1;int *temp (int*)malloc(sizeof(int)*range);if (NULL temp){assert(0);return;}//3---空间位置里全部置为0memset(temp, 0, sizeof(int)*range);//memeset 按一个一个字节赋值赋值0可以赋值其他值不行例如100给一个字节赋值100//4--统计每个数据出现的次数for (int i 0; i size; i){temp[array[i] - minVal];}//5--回收数据int index 0;for (int i 0; i range; i){while (temp[i]--) //当前元素值不为0说明该下标还有个数 {array[index] i minVal;}}free(temp);
}计数排序参考链接
排序总结
