数据结构六大排序

 

 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 (gap>1){//每次对gap折半操作gap = gap / 2;//或者gap=gap/3+1    //单趟排序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[keyi+1,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[keyi+1,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)
{stack<int> 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);}//当mid+1>=右区间则证明右区间已经排好序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] > key&&++prev != 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, j=midIndex+1, k = startIndex;while(i!=midIndex+1 && j!=endIndex+1) {if(sourceArr[i] > sourceArr[j])tempArr[k++] = sourceArr[j++];elsetempArr[k++] = sourceArr[i++];}while(i != midIndex+1)tempArr[k++] = sourceArr[i++];while(j != endIndex+1)tempArr[k++] = sourceArr[j++];for(i=startIndex; i<=endIndex; 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, midIndex+1, 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(i=0; i<8; i++)printf("%d ", a[i]);printf("\n");return 0;
}

时间复杂度 O(nlogn)

空间复杂度 O(n)归并排序需要一个与原数组相同长度的数组做辅助来排序。