电子商务网站建设专业主修课程,郑州专业建网站,手机微网站建设多少钱,福建交科建设有限公司官方网站吾日三省吾身#xff1a;高否#xff1f;富否#xff1f;帅否#xff1f;答曰#xff1a;否。滚去学习!!!(看完这篇文章先)目前只有C和C的功底#xff0c;暂时还未开启新语言的学习#xff0c;但是大同小异#xff0c;语法都差不多。目录#xff1a;一.排序定义二.排序…吾日三省吾身高否富否帅否答曰否。滚去学习!!!(看完这篇文章先)目前只有C和C的功底暂时还未开启新语言的学习但是大同小异语法都差不多。目录一.排序定义二.排序算法的评价指标(最后总结)1.算法的稳定性2.时间复杂度和空间复杂度三.七大排序算法1.冒泡排序2.选择排序3.插入排序4.希尔排序5.归并排序6.快速排序7.堆排序 稳定性及其复杂度总结一.排序定义排序(sort):排序就是重新排列表中的元素使得元素满足按关键字有序的过程。二.排序算法的评价指标(最后总结)1.算法的稳定性 若待排序表中有两个元素R1和R2其对应的关键字相同即k1 k2,且在排序前R1在R2的前面若使用某一排序算法排序后R1仍然在R2的前面则称这个排序算法是稳定的否则称排序算法是不稳定的。 意思就是两个相同的关键字在排序前后位置不变,排序前在前面那么排序前就在前面后面就在后面。如果排序前后两个数的位置不相同那么此算法就是不稳定的。2.时间复杂度和空间复杂度三.七大排序算法 ·排序算法分为内部排序和外部排序内部排序的时候哦数据都存储在内存中外部排序中由于数据过多而无法全部放入内存。冒泡排序冒泡排序Bubble Sort也是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端。冒泡排序还有一种优化算法就是立一个 flag当在一趟序列遍历中元素没有发生交换则证明该序列已经有序。冒泡排序算法步骤从数组的第一个元素开始依次比较每对相邻的元素如果前面的元素大于后面的元素就交换它们的位置。对数组中的每一对相邻元素重复步骤1直到最后一个元素。此时数组中最后一个元素应该是最大的元素。针对除去已排序的最后一个元素的剩余元素重复步骤1和步骤2直到整个数组都被排序。注意当输入的数据是正序这个时候排序最快当输入的数据是反序这个时候排序最慢C语言实现#include stdio.h
void bubble_sort(int arr[], int len) {int i, j, temp;for (i 0; i len - 1; i)for (j 0; j len - 1 - i; j)if (arr[j] arr[j 1]) {temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}
}
int main() {int arr[] { 2, 4, 6, 8, 5, 7,9 , 1,3,10};int len (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);int i;for (i 0; i len; i)printf(%d , arr[i]);return 0;
}C实现#include iostream
using namespace std;
templatetypename T //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于()运算符
void bubble_sort(T arr[], int len) {int i, j;for (i 0; i len - 1; i)for (j 0; j len - 1 - i; j)if (arr[j] arr[j 1])swap(arr[j], arr[j 1]);
}
int main() {int arr[] {2, 4, 6, 8, 5, 7,9 , 1,3,10 };int len (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);for (int i 0; i len; i)cout arr[i] ;cout endl;return 0;
}时间复杂度最坏情况O(N^2) 最好情况O(N)空间复杂度O(1)2.选择排序选择排序Selection Sort是一种简单的排序算法。其基本思想是首先从未排序的元素中找到最小的元素然后将其放到已排序的序列末尾然后再从剩余未排序的元素中继续找到最小的元素将其放到已排序的序列末尾以此类推直到所有元素都排好序。选择排序的算法步骤遍历待排序的数组从第一个元素开始在未排序的元素中找到最小的元素记录其下标将最小的元素与第一个元素交换位置接着在未排序的元素中继续寻找最小的元素记录其下标将最小的元素与第二个元素交换位置重复步骤 4-5 直到所有元素都排序完成C语言实现void swap(int *a,int *b) //交换两个数
{int temp *a;*a *b;*b temp;
}
void selection_sort(int arr[], int len)
{int i,j;for (i 0 ; i len - 1 ; i){int min i;for (j i 1; j len; j) //走访未排序的元素if (arr[j] arr[min]) //找到目前最小值min j; //记录最小值swap(arr[min], arr[i]); //做交換}
}C实现templatetypename T
void selection_sort(std::vectorT arr) {for (int i 0; i arr.size() - 1; i) {int min i;for (int j i 1; j arr.size(); j)if (arr[j] arr[min])min j;std::swap(arr[i], arr[min]);}
}3.插入排序插入排序Insertion Sort排序算法其思想是从第二个元素开始依次将其插入到已经有序的序列中。插入排序的算法步骤1第二个元素开始将该元素视为一个有序序列。2将该元素与它前面的元素进行比较如果前面的元素比它大则交换位置。3继续向前比较直到该元素找到了合适的位置。4对下一个元素重复上述过程直到所有元素都排好序为止。C语言实现void insertion_sort(int arr[], int len){int i,j,key;for (i1;ilen;i){key arr[i];ji-1;while((j0) (arr[j]key)) {arr[j1] arr[j];j--;}arr[j1] key;}
}C实现void insertion_sort(int arr[],int len){for(int i1;ilen;i){int keyarr[i];int ji-1;while((j0) (keyarr[j])){arr[j1]arr[j];j--;}arr[j1]key;}
}时间复杂度最坏情况下为O(N*N)此时待排序列为逆序或者说接近逆序 最好情况下为O(N)此时待排序列为升序或者说接近升序。空间复杂度O(1)4.希尔排序希尔排序Shell Sort是插入排序的一种改进版本也被称为“缩小增量排序”。它的基本思想是先将待排序的序列分割成若干个子序列对每个子序列进行插入排序然后逐步缩小子序列的长度最终完成排序。算法步骤1.选择一个增量序列 t1t2……tk其中 ti tj, t k 12.按增量序列个数 k对序列进行 k 趟排序3.每趟排序根据对应的增量 ti将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插 入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。C语言实现void shell_sort(int arr[], int len) {int gap, i, j;int temp;for (gap len 1; gap 0; gap 1)for (i gap; i len; i) {temp arr[i];for (j i - gap; j 0 arr[j] temp; j - gap)arr[j gap] arr[j];arr[j gap] temp;}
}C实现templatetypename T
void shell_sort(T array[], int length) {int h 1;while (h length / 3) {h 3 * h 1;}while (h 1) {for (int i h; i length; i) {for (int j i; j h array[j] array[j - h]; j - h) {std::swap(array[j], array[j - h]);}}h h / 3;}
}时间复杂度平均O(N^1.3)空间复杂度O(1)5.归并排序 归并排序Merge Sort是一种分治算法其基本思想是将待排序序列分成若干个子序列分别进行排序然后将子序列合并成一个有序序列。归并排序算法步骤将待排序序列分成两个子序列分别进行递归排序。合并两个有序子序列得到一个更长的有序序列。重复上述过程直到所有子序列都有序。int min(int x, int y) {return x y ? x : y;
}
void merge_sort(int arr[], int len) {int *a arr;int *b (int *) malloc(len * sizeof(int));int seg, start;for (seg 1; seg len; seg seg) {for (start 0; start len; start seg * 2) {int low start, mid min(start seg, len), high min(start seg * 2, len);int k low;int start1 low, end1 mid;int start2 mid, end2 high;while (start1 end1 start2 end2)b[k] a[start1] a[start2] ? a[start1] : a[start2];while (start1 end1)b[k] a[start1];while (start2 end2)b[k] a[start2];}int *temp a;a b;b temp;}if (a ! arr) {int i;for (i 0; i len; i)b[i] a[i];b a;}free(b);
}C实现templatetypename T
void merge_sort(T arr[], int len) {T *a arr;T *b new T[len];for (int seg 1; seg len; seg seg) {for (int start 0; start len; start seg seg) {int low start, mid min(start seg, len), high min(start seg seg, len);int k low;int start1 low, end1 mid;int start2 mid, end2 high;while (start1 end1 start2 end2)b[k] a[start1] a[start2] ? a[start1] : a[start2];while (start1 end1)b[k] a[start1];while (start2 end2)b[k] a[start2];}T *temp a;a b;b temp;}if (a ! arr) {for (int i 0; i len; i)b[i] a[i];b a;}delete[] b;
}C(递归版)void Merge(vectorint Array, int front, int mid, int end) {// preconditions:// Array[front...mid] is sorted// Array[mid1 ... end] is sorted// Copy Array[front ... mid] to LeftSubArray// Copy Array[mid1 ... end] to RightSubArrayvectorint LeftSubArray(Array.begin() front, Array.begin() mid 1);vectorint RightSubArray(Array.begin() mid 1, Array.begin() end 1);int idxLeft 0, idxRight 0;LeftSubArray.insert(LeftSubArray.end(), numeric_limitsint::max());RightSubArray.insert(RightSubArray.end(), numeric_limitsint::max());// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]for (int i front; i end; i) {if (LeftSubArray[idxLeft] RightSubArray[idxRight]) {Array[i] LeftSubArray[idxLeft];idxLeft;} else {Array[i] RightSubArray[idxRight];idxRight;}}
}void MergeSort(vectorint Array, int front, int end) {if (front end)return;int mid (front end) / 2;MergeSort(Array, front, mid);MergeSort(Array, mid 1, end);Merge(Array, front, mid, end);
}6.快速排序快速排序Quick Sort是一种常用的排序算法也是一种分治算法。其基本思想是选择一个基准元素将待排序序列分成两个子序列使得一个子序列中所有元素都比基准元素小另一个子序列中所有元素都比基准元素大然后递归地对子序列进行排序。具体实现过程如下选择一个基准元素一般选择第一个元素或者随机选择一个元素。将序列中所有比基准元素小的元素放在基准元素的左边所有比基准元素大的元素放在右边。对基准元素的左右两边重复上述过程直到每个子序列只剩下一个元素。C语言实现typedef struct _Range {int start, end;
} Range;Range new_Range(int s, int e) {Range r;r.start s;r.end e;return r;
}void swap(int *x, int *y) {int t *x;*x *y;*y t;
}void quick_sort(int arr[], const int len) {if (len 0)return; Range r[len];int p 0;r[p] new_Range(0, len - 1);while (p) {Range range r[--p];if (range.start range.end)continue;int mid arr[(range.start range.end) / 2]; int left range.start, right range.end;do {while (arr[left] mid) left; while (arr[right] mid) --right; if (left right) {swap(arr[left], arr[right]);left;right--; }} while (left right);if (range.start right) r[p] new_Range(range.start, right);if (range.end left) r[p] new_Range(left, range.end);}
}C实现int Paritition1(int A[], int low, int high) {int pivot A[low];while (low high) {while (low high A[high] pivot) {--high;}A[low] A[high];while (low high A[low] pivot) {low;}A[high] A[low];}A[low] pivot;return low;}void QuickSort(int A[], int low, int high) //快排母函数{if (low high) {int pivot Paritition1(A, low, high);QuickSort(A, low, pivot - 1);QuickSort(A, pivot 1, high);}}7.堆排序堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列算法步骤1创建一个堆 H[0……n-1]2把堆首最大值和堆尾互换3把堆的尺寸缩小 1并调用 shift_down(0)目的是把新的数组顶端数据调整到相应位置4重复步骤 2直到堆的尺寸为 1。C语言代码实现#include stdio.h
#include stdlib.hvoid swap(int *a, int *b) {int temp *b;*b *a;*a temp;
}void max_heapify(int arr[], int start, int end) {// 建立父節點指標和子節點指標int dad start;int son dad * 2 1;while (son end) { // 若子節點指標在範圍內才做比較if (son 1 end arr[son] arr[son 1]) // 先比較兩個子節點大小選擇最大的son;if (arr[dad] arr[son]) //如果父節點大於子節點代表調整完畢直接跳出函數return;else { // 否則交換父子內容再繼續子節點和孫節點比較swap(arr[dad], arr[son]);dad son;son dad * 2 1;}}
}void heap_sort(int arr[], int len) {int i;// 初始化i從最後一個父節點開始調整for (i len / 2 - 1; i 0; i--)max_heapify(arr, i, len - 1);// 先將第一個元素和已排好元素前一位做交換再重新調整直到排序完畢for (i len - 1; i 0; i--) {swap(arr[0], arr[i]);max_heapify(arr, 0, i - 1);}
}int main() {int arr[] { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);int i;for (i 0; i len; i)printf(%d , arr[i]);printf(\n);return 0;
}C实现#include iostream
#include algorithm
using namespace std;void max_heapify(int arr[], int start, int end) {//建立父节点和字节点int dad start;int son dad * 2 1;while (son end) { if (son 1 end arr[son] arr[son 1]) // 比较两个子节点大小选择大的son;if (arr[dad] arr[son]) // 如果父节点大于子节点代表完整退出函数return;else { swap(arr[dad], arr[son]);dad son;son dad * 2 1;}}
}void heap_sort(int arr[], int len) {for (int i len / 2 - 1; i 0; i--)max_heapify(arr, i, len - 1);for (int i len - 1; i 0; i--) {swap(arr[0], arr[i]);max_heapify(arr, 0, i - 1);}
}int main() {int arr[] { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);for (int i 0; i len; i)cout arr[i] ;cout endl;return 0;
}稳定性以及复杂度大话数据结构关于排序算法的的总结
