建设网站需要什么技术,建设企业网站报价,专业网络优化,可以做网站的编程有什么1.插入排序 思路#xff1a;
从第一个元素开始认为是有序的#xff0c;去一个元素tem从有序序列从后往前扫描#xff0c;如果该元素大于tem#xff0c;将该元素一刀下一位#xff0c;循环步骤3知道找到有序序列中小于等于的元素将tem插入到该元素后#xff0c;如果已排序… 1.插入排序 思路
从第一个元素开始认为是有序的去一个元素tem从有序序列从后往前扫描如果该元素大于tem将该元素一刀下一位循环步骤3知道找到有序序列中小于等于的元素将tem插入到该元素后如果已排序所有元素都大于tem则将插入到下标为0的位置 如此重复。 红线前认为是有序的 。
void InsertSort(int* arr, int n)
{for (int i 0; i n - 1; i){//记录有序序列最后一个元素的下标int end i;//待插入的元素int tem arr[end 1];//单趟排while (end 0){//比插入的数大就向后移if (tem arr[end]){arr[end 1] arr[end];end--;}//比插入的数小跳出循环else{break;}}//tem放到比插入的数小的数的后面arr[end 1] tem;//代码执行到此位置有两种情况://1.待插入元素找到应插入位置break跳出循环到此//2.待插入元素比当前有序序列中的所有元素都小while循环结束后到此}
}插入排序待排序列接近逆序时是最坏情况O(N*N)接近升序是最快为O(N)。
空间复杂度O(1) 2.希尔排序
思路:
将待排序序列进行预排序再进行插入排序。选定一个整数gap作为组距将距离为gap的元素认为是一组进行直接插入排序再取一个比原gap小的新gap重复操作 当gap为1时预排序完毕最后进行一次直接插入排序。 //希尔排序
void ShellSort(int* arr, int n)
{int gap n;while (gap1){//每次对gap折半操作gap gap / 2;//或者gapgap/31 //单趟排序for (int i 0; i n - gap; i){int end i;int tem arr[end gap];while (end 0){if (tem arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tem;}}
}时间复杂度平均O(N^1.3)(记住就行了) 空间复杂度O(1) 3.选择排序 每次从待排序列中选出一个最小值和最大值分别放在序列头和尾。用到SWAP
//选择排序
void swap(int* a, int* b)
{int tem *a;*a *b;*b tem;
}
void SelectSort(int* arr, int n)
{//保存参与单趟排序的第一个数和最后一个数的下标int begin 0, end n - 1;while (begin end){//保存最大值的下标int maxi begin;//保存最小值的下标int mini begin;//找出最大值和最小值的下标for (int i begin; i end; i){if (arr[i] arr[mini]){mini i;}if (arr[i] arr[maxi]){maxi i;}}//最小值放在序列开头swap(arr[mini], arr[begin]);//防止最大的数在begin位置被换走if (begin maxi){maxi mini;}//最大值放在序列结尾swap(arr[maxi], arr[end]);begin;--end;}
}注意因为先交换最小值可能导致一开始最大值在gegin最小值交换后最大值也被换走。所以加一句判断如果最大值是begin则交换最大值时先把maxi赋值成mini才正确。
时间复杂度O(N^2) 空间复杂度O(1) void bubble_sort(int* arr, int sz)
{int i 0;for (i 0; i sz-1; i){//每一趟冒泡排序int j 0;for (j 0; j sz-i-1; j){if (arr[j]arr[j 1]){int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;}//两两相邻元素进行交换}}}时间复杂度最坏情况O(N^2) 最好情况O(N) 空间复杂度O(1) 5.堆排序 参考(77条消息) 二叉树——堆_RoseLJ的博客-CSDN博客 6.快速排序 1左右指针法 思路
1.定义一个key一般是最左边或最右。
2.定义一个begin和end重点如果选择最左边的数据为key则需要end先走如果选择最右边的数据为key则需要begin先走
3.走的过程中end遇到小于key的树停下begin开始走直到遇到一个大于key的数begin和end内容交换然后end再开始走如此进行下去直到最终begin和end相遇相遇后将相遇点与key交换此步骤为选取左边为key时。此时key左边都是小于key的树右边都是大于kkey的数。
4.将key的左右序列重复以上操作知道左右序列只有一个数据或者不存在时停止。
//快速排序 hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end)
{//只有一个数或区间不存在if (begin end)return;int left begin;int right end;//选左边为keyint keyi begin;while (begin end){//右边选小 等号防止和key值相等 防止顺序begin和end越界while (arr[end] arr[keyi] begin end){--end;}//左边选大while (arr[begin] arr[keyi] begin end){begin;}//小的换到右边大的换到左边swap(arr[begin], arr[end]);}swap(arr[keyi], arr[end]);keyi begin;//[left,keyi-1]keyi[keyi1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr,keyi 1,right);
}时间复杂度
嵌套过程类似于二叉树高度为logN,每层约有N个数
2挖坑法递归
思路与左右指针法类似
1.选出一个数最左或最右放在key中在该数据位置形成一个坑。
2.定义l和r如果在最左边挖坑则需要r先走在最右边挖坑需要l先走。
后面思路类似于双指针。 //快速排序法 挖坑法
void QuickSort1(int* arr, int begin, int end)
{if (begin end)return;int left begin,right end;int key arr[begin];while (begin end){//找小while (arr[end] key begin end){--end;}//小的放到左边的坑里arr[begin] arr[end];//找大while (arr[begin] key begin end){begin;}//大的放到右边的坑里arr[end] arr[begin];}arr[begin] key;int keyi begin;//[left,keyi-1]keyi[keyi1,right]QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi 1, right);
}快速排序优化三数取中
在有序或接近有序时快速排序效率较低利用三数取中可提高效率。
三数取中就是从待排序列的第一个元素中间元素和最后一个元素中选出大小位于中间的元素把这个元素作为基准值key。
int GetMid(int* a,int left,int mid,int right)
{if(a[left] a[mid]){if(a[mid] a[right]){return mid;}else if(a[left] a[right]){return right;}else{return left;}}else //a[left] a[mid]{if(a[mid] a[right]){return mid;}else if(a[left] a[right]){return right;}else{return left;}}
} 挖坑法非递归
//单趟排
int PartSort(int* arr, int begin, int end)
{int key arr[begin];while (begin end){while (key arr[end] begin end){--end;}arr[begin] arr[end];while (key arr[begin] begin end){begin;}arr[end] arr[begin];}arr[begin] key;int meeti begin;return meeti;
}void QuickSortNoR(int* arr, int begin, int end)
{stackint st;//先入右边st.push(end);//再入左边st.push(begin);while (!st.empty()){//左区间int left st.top();st.pop();//右区间int right st.top();st.pop();//中间数int mid PartSort(arr, left, right);//当左区间mid-1则证明左区间已经排好序了if (left mid - 1){st.push(mid - 1);st.push(left);}//当mid1右区间则证明右区间已经排好序if (right mid 1){st.push(right);st.push(mid 1);}}
}3 前后指针法 思路
1.选出key最左或最右。
2.cur找比key小的找到停下来。
3.prev交换prev位置和cur位置的值。
int partion(int* array,int begin,int end)//待排序数组的首指针待排序的首尾元素下标
{int key array[begin];//选取第一个元素为基准值int prev begin;//前指针int cur prev 1;//后指针whiel(cur end){if(array[cur] keyprev ! cur)//如果cur的值小于key判断prev的值是否等于cur//若不等于则交换prev和cur的值swap(array,prev,cur);cur;//cur向后移动}//当跳出循环时说明prev及之前的值都是小于基准值的数则交换prev指向的值和基准值swap(array,prev,begin);return prev;//返回此时基准值的下标便于下次递归调用时分组
}void quicksort(int* array,int begin,int end)
{if(begin end)return ;int keypos partion(array,begin,end);quicksort(array,begin,keypos - 1);quicksort(array,keypos 1,end);
}6.归并排序
思路
1.将待排序的线性表不断切分成诺干个子表知道每个子表只包含一个元素这是可以认为包含一个元素的子表是有序表。
2.将有序表两两合并每合并一次就产生一个新的更长的有序表重复合并知道最后只剩下一个表。
1递归实现 void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){int i startIndex, jmidIndex1, k startIndex;while(i!midIndex1 j!endIndex1) {if(sourceArr[i] sourceArr[j])tempArr[k] sourceArr[j];elsetempArr[k] sourceArr[i];}while(i ! midIndex1)tempArr[k] sourceArr[i];while(j ! endIndex1)tempArr[k] sourceArr[j];for(istartIndex; iendIndex; i)sourceArr[i] tempArr[i];
}//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) {int midIndex;if(startIndex endIndex) {midIndex startIndex (endIndex-startIndex) / 2;//避免溢出intMergeSort(sourceArr, tempArr, startIndex, midIndex);MergeSort(sourceArr, tempArr, midIndex1, endIndex);Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);}
}int main(int argc, char * argv[]) {int a[8] {50, 10, 20, 30, 70, 40, 80, 60};int i, b[8];MergeSort(a, b, 0, 7);for(i0; i8; i)printf(%d , a[i]);printf(\n);return 0;
}
时间复杂度 O(nlogn)
空间复杂度 O(n)归并排序需要一个与原数组相同长度的数组做辅助来排序。
