硅谷网站开发薪酬,网站建设 数据可视化,wordpress 图片弹窗点击广告才能,wordpress alchem一.冒泡排序
原理图#xff1a; 实现代码#xff1a;
/* 冒泡排序或者是沉底排序 *//* int arr[]: 排序目标数组,这里元素类型以整型为例; int len: 元素个数 */
void bubbleSort (elemType arr[], int len) {//为什么外循环小于len-1次#xff1f;//考虑临界情况#xf…一.冒泡排序
原理图 实现代码
/* 冒泡排序或者是沉底排序 *//* int arr[]: 排序目标数组,这里元素类型以整型为例; int len: 元素个数 */
void bubbleSort (elemType arr[], int len) {//为什么外循环小于len-1次//考虑临界情况就是要循环到len-1个沉底/冒泡则排序完毕for (int i0; ilen-1; i) {//为什么内循环小于等于len-2-i次//考虑临界情况第一次循环最后是索引为len-2与len-1进行比较所以第一次循环到len-2//每循环一次多沉底/冒泡一个所以每循环完一次要多减去1也就是多减去i所以为len-2-ifor (int j0; jlen-2-i; j) { //相邻元素比较符合条件进行交换数值大的元素沉底数值小的元素冒泡if (arr[j] arr[j1]) { int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}
二.插入排序 原理图 实现代码
// 插入排序函数n是数组的长度
void insertionSort(int arr[], int n) {//先对第二个元素进行插入索引比实际位置少一直到对n个元素进行插入for (int i 1; i n; i) {int key arr[i]; // 当前要插入的元素j i-1;// 将当前元素与前面的比较将比当前元素大的元素往后移动自己往前移动// 直到找到合适的位置或者遍历到数组的开头while (int j 0 arr[j] key) {arr[j1] arr[j]; // 当前元素比key大向后移动一位j j-1; // 继续向前比较}arr[j1] key; // 将当前元素插入到正确的位置}
}三.选择排序
原理图 实现代码
void selectionSort(int arr[], int n) {// 遍历数组从第一个元素到倒数第二个元素要排序n-1次n-1个排好才算全部排好for (int i 0; i n - 1; i) {int minIndex i;//假设当前循环开始时第一个元素为最小值// 在未排序部分寻找最小值for (int j i 1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}// 如果最小值不是当前循环的第一个元素则进行交换if (minIndex ! i) {// 交换两个元素的位置int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}}
}上面三种简单排序算法在最坏情况及平均情况下都需要O()计算时间。 下面讨论的排序算法它在平均情况下需要O(nlogn)时间。下面这些是目前最快的排序。 四.快速排序--分治法挖坑填数 原理 去B站看其中快速排序的哪一节 分治法大问题分解成各个小问题对小问题求解使得大问题得以解决。 实现代码
#includeiostream
using namespace std;
void PrintArray(int arr[],int len) {for(int i0; ilen; i) {coutarr[i] ;}coutendl;
}
//快速排序,从小到大
void QuickSort(int arr[],int start,int end) {//i和j是索引的值也可以看做是指针//先让它们指向要排序数据的首尾int istart;int jend;//基准数这里取数据的start位置,同时也是此时i的位置//挖坑填数时挖出来的第一个数也就是第一个的坑为基准数的位置/也是此时start和i的位置int temparr[start];//保证参数输入正确即startend,否则不执行if(ij) {//只要i和j不重合就不断地移动j,挖坑填数,移动i,挖坑填数...//最后做到基准数小的数都在基准数的左边比基准数大的数都在基准数的右边while(ij) //移动指针j,从右向左找比基准数小的元素,比基准数大继续左移//直到遇到比基准数小的元素才跳出循环用该元素填坑while(ijarr[j]temp) {j--;}//用j位置的数据给i的坑填数(将j的数据赋值给i)j变成坑if(ij) {arr[i]arr[j];}//移动指针i,从左向右找比基准数大的数,比基准数小i继续右移//直到遇到比基准数小的元素才跳出循环用该元素填坑while(ijarr[i]temp) {i;}//用i位置的数据给j的坑填数(将i的数据赋值给j)j变成坑if(ij) {arr[j]arr[i];}}//最后i和j重叠的位置就是基准数的位置把基准数放到i的位置填上最后一个坑arr[i]temp;//递归//1.对左半部分进行快速排序QuickSort(arr,start,i-1);//2.对右半部分进行快速排序QuickSort(arr,i1,end); }
}
int main() {int myArr[] {4,2,8,0,5,7,1,3,9};int lensizeof(myArr)/sizeof(int);PrintArray(myArr,len);QuickSort(myArr,0,len-1);PrintArray(myArr,len);return 0;
} 五.归并排序/合并排序--分治法合并两个有序序列
基本思想分治法将两个有序序列合并成一个有序序列 怎么合并呢 就是开辟一块临时的存储空间。就比如有两个身高从低到高的队伍要合并成一个也是身高从小到高的队伍就先将每个队伍的第一个人比较身高然后低的进去然后第二个人再与另一个队的第一个人比较身高低的进去。。。以此类推差不多就是这样。 去B站看其中合并排序的哪一节 #includeiostream
#includetime.h
#includesys/timeb.h
using namespace std;
#define MAX 10
//创建数组
int* CreatArray() {srand((unsigned int)time(NULL));int* arr(int*)malloc(sizeof(int)*MAX);for(int i0; iMAX; i) {arr[i]rand()%MAX;}return arr;
}
//打印
void PrintArray(int arr[],int len) {for(int i0; ilen; i) {coutarr[i] ;}coutendl;
}
//合并算法从小到大
//int *temp--临时的存储空间
void Merge(int arr[],int start,int end,int mid,int *temp) {//一.将序列拆分为ij两个序列 int i_startstart;//i序列的头指针 int i_endmid;//i序列的尾指针 int j_startmid1;//j序列的头指针 int j_endend;//j序列的尾指针 int length0;//表示辅助空间有多少个元素//二.合并两个有序序列,并且使得合并后仍然有序//遍历到其中一个序列空为止while(i_starti_endj_startj_end) {//如果i指针指向的元素比j小则先推出到辅助空间中if(arr[i_start]arr[j_start]) {//将数据存到辅助空间中temp[length]arr[i_start];//辅助空间长度加一length;//i序列指针往后移判断下一个推入辅助空间的元素i_start;} else {//如果j指针指向的元素比i小则先推出到辅助空间中//将数据存到辅助空间中temp[length]arr[j_start];//辅助空间长度加一length;//j序列指针往后移判断下一个要推入辅助空间的元素j_start;}}//三.只有一个序列为空说明有一个序列里面还有剩下的元素,要将剩下的元素也存到辅助空间 //如果i这个序列的头指针仍然在尾指针之前说明里面还有元素while (i_starti_end) {//将数据存到辅助空间中temp[length]arr[i_start];//辅助空间长度加一length;//i序列指针往后移判断下一个推入辅助空间的元素i_start;}//如果j这个序列的头指针仍然在尾指针之前说明里面还有元素while(j_startj_end) {//将数据存到辅助空间中temp[length]arr[j_start];//辅助空间长度加一length;//j序列指针往后移判断下一个要推入辅助空间的元素j_start;}//四.把辅助空间中的数据覆盖到原空间for(int i0;ilength;i){arr[starti]temp[i];}
}
//归并排序
void MergeSort(int arr[],int start,int end,int* temp) {if(startend) {return;}int mid(startend)/2;//分组//左半边MergeSort(arr,start,mid,temp);//右半边MergeSort(arr,mid1,end,temp);//合并Merge(arr,start,end,mid,temp);}
int main() {int* myArrCreatArray();PrintArray(myArr,MAX);//辅助空间,来存储合并后的有序序列。int * temp(int*)malloc(sizeof(int)* MAX) ;MergeSort(myArr,0,MAX-1,temp);PrintArray(myArr,MAX);//释放空间free(temp);free(myArr);
}
六.希尔排序--分治法插入排序插入排序的提升版 [算法]六分钟彻底弄懂希尔排序简单易懂 20希尔排序 #include stdio.h
void shellSort(int arr[],int length) {int increasementlength;//确定分组的增量你可以用你喜欢的增量我这里取长度除以2 increasementincreasement/2;//增量小于1停止也就是最后对一整组进行插入排序后停止 while(increasement1) {//遍历每一组for(int i0; iincreasement; i) {// 对每一组进行快速排序//遍历当前这组的元素 for(int jiincreasement; jlength; jincreasement) {// 如果当前元素小于前一个元素则进行插入操作if(arr[j]arr[j-increasement]) {int temparr[j];int k;// 将大于temp的元素向后移动for(kj-increasement; k0temparr[k]; k-increasement) {arr[kincreasement]arr[k];}// 插入temp到正确的位置arr[kincreasement]temp;}}}//缩小增量 increasementincreasement/2;}
}
void printArray(int arr[], int n) {for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {12, 34, 54, 2, 3};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: );printArray(arr, n);shellSort(arr, n);printf(排序后的数组: );printArray(arr, n);return 0;
}
为什么分组后的插入排序会快呢 因为插入排序在元素序列基本有序和元素个数比较小的时候速度较快而分组就创造了这种条件。
总结
可以发现下面三种快的排序平均情况下的时间复杂度都为Onlogn都使用了分治法将一个大问题分为几个相同的小问题分而治之。
