天勤2022数据结构（七）排序
生活随笔
收集整理的這篇文章主要介紹了
天勤2022数据结构（七）排序
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔
天勤2022數(shù)據(jù)結(jié)構(gòu)（七）排序
- 前言
- 易混知識點
- 一、基礎算法
- 二、綜合應用題
- 總結(jié)
前言
穩(wěn)定：guibing
不穩(wěn)定：快 些兒 選 一堆朋友
易混知識點
- 高效：直接插入 ??冒泡
- 低效：快速排序
一、基礎算法
插入排序
直接插入排序
折半插入排序
減少 比較 次數(shù)
希爾排序
不能保證每趟排序至少能將一個關(guān)鍵字放在其最終位置上
void shellSort(int arr[], int n){int temp;for(int gap = n/2; gap>0; gap/=2){for(int i = gap; i<n; i++){temp = arr[i];int j;for(j=i; j>=gap && arr[j-gap]>temp; j-=gap){arr[j] = arr[j - gap];}arr[j] = temp;}} }選擇排序
簡單選擇排序
比較次數(shù) 與 初始序列 無關(guān)（全比較）
堆排序
// arr[low]-arr[high] 對low上的結(jié)點進行調(diào)整 void Sift(int arr[], int low, int high){int i = low, j = 2*i+1;int temp = arr[i];while(j <= high){if(j < high && arr[j] < arr[j+1]){j++;}if(temp < arr[j]){arr[i] = arr[j];i = j;j = 2 * i + 1;}else{break;} }arr[i] = temp; }void heapSort(int arr[], int n) {int i, temp;// 建堆for(i = n/2-1; i>=0; i--){Sift(arr, i, n-1);}// 維護(逐個移出堆頂元素后的維護)for(i = n-1; i>0; i--){temp = arr[0];arr[0] = arr[i];arr[i] = temp;Sift(arr, 0, i-1); } }交換排序
冒泡排序
排序趟數(shù) 與 序列的原始狀態(tài) 有關(guān)
快速排序
有序情況下 退化為冒泡排序
遞歸次數(shù) 與 劃分后分區(qū)的處理順序 無關(guān) （視為二叉樹，多少個結(jié)點，遍歷多少次 ）
[真題] 最好用 順序結(jié)構(gòu)存儲
一趟之后 確定一個關(guān)鍵字 左邊的（可以沒有）小于 ?? 右邊的（可以沒有）大于
二路歸并排序
void mergeSort(int A[], int low, int high){if(low < high){int mid = (low + high)/2;mergeSort(A, low, mid);mergeSort(A, mid+1, high);merge(A, low, mid, high);} }void merge(int A[], int low, int mid, int high){int i, j, k;int len1 = mid - low + 1;int len2 = high - mid;int L[len1], R[len2];for(i = 0; i<len1; i++)L[i] = A[low+i]; for(j = 0; j<len2; j++)R[j] = A[mid + 1 + j];i = 0; j = 0; k = low;while(i<len1 && j<len2){if(L[i] <= R[i]){A[k] = L[i];i++;}else{A[k] = R[j];j++;}k++;} while(i<len1) A[k++] = L[i++];while(j<len2) A[k++] = R[j++]; }【易錯點】
?L[i] = A[low+i];
?R[j] = A[mid + 1 + j];
基數(shù)排序
不需要關(guān)鍵字的比較
二、綜合應用題
總結(jié)
提示：這里對文章進行總結(jié)：
總結(jié)
以上是生活随笔為你收集整理的天勤2022数据结构（七）排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [转]flashCS4版本一个网站导航
- 下一篇： 小规模纳税人和一般纳税人的区别