十大排序大总结
深蓝de星球
8年前
<h2><strong>BubbleSort（冒泡排序）</strong></h2> <p>定义：在同一个数组中，从数组第一个数开始，相邻两个数进行比较，按照小左大右或者大右小左的顺序，依次循环遍历，进行排序！</p> <pre> <code class="language-cpp">void BubbleSort(int *arr,int Length) { int i = 0; int j = 1; int sys = 0; for (i = 0; i < Length-1; i++) { for (j = 0; j < Length-i-1; j++) { if (arr[j]>arr[j+1]) { arr[j] = arr[j]^arr[j+1]; arr[j+1] = arr[j]^arr[j+1]; arr[j] = arr[j]^arr[j+1]; } } sys++; } return ; }</code></pre> <h3><strong>改进版冒泡排序</strong></h3> <p>在原有的基础上，我们添加了标记！记录了最后一次交换的位置！</p> <p>如5，1，4，6，3，2，7，8，9。最后一次交换的位置在2处，并且设定我们每次循环的到2，不对7，8，9</p> <p>进行比较，节省我们运算的效率！</p> <p>冒泡排序是对 <strong>全部已经排好</strong> 序列排序最快的</p> <pre> <code class="language-cpp">void BetterBubbleSort(int *arr,int Length) { int i = 0; int j = 1; int pmark; int sys = 0; for (; i < Length-1; i++) { pmark = 0; for (j = 0; j < Length-i-1; j++) { if (arr[j]>arr[j+1]) { arr[j] = arr[j]^arr[j+1]; arr[j+1] = arr[j]^arr[j+1]; arr[j] = arr[j]^arr[j+1]; pmark = j+1; } } i == Length - pmark - 1; sys++; } return ; }</code></pre> <h3>不带中间变量实现两个相同类型不同值变量间的互换</h3> <ol> <li>加减法</li> </ol> <pre> <code class="language-cpp">int a = 5; int b = 3; a = a+b; b = a-b; a = a-b;</code></pre> <ol> <li>异或^</li> </ol> <pre> <code class="language-cpp">int a = 5; int b = 3; a = a^b; b = a^b; a = a^b;</code></pre> <p>ps:若对于 *a ， *b 值进行交换， *a ， *b 不能指向同一块地址空间！</p> <h2><strong>SelectSort选择排序</strong></h2> <p>首先，用第一个数去和所有数进行比较，选出其中最小的数，放在第一位，在用第二个数去和全部数进行比较，最小的放在第二位，依次循环遍历！</p> <pre> <code class="language-cpp">void SelectSort(int *Arr,int nLength) { int i = 0; int j = 1; int min = 0; for (i = 0; i < nLength; i++) { for (j = i; j < nLength-1; j++) { if (Arr[i] > Arr[j]) { Arr[j] = Arr[j]^Arr[i]; Arr[i] = Arr[j]^Arr[i]; Arr[j] = Arr[j]^Arr[i]; } } } }</code></pre> <p>代码优化：把每次都交换的位置，换成比较完之后，有一个int记下来，不用每次比较完进行交换，而是最后直接用记录的数组下标进行交换！</p> <h2><strong>InsertSort插入排序</strong></h2> <p>把当前数组分成两部分，第一部分有序，第二部分无序，将无序数组依次插入有序数组里去！</p> <p>例如数组：10，20，3，8，55.用一个temp保存无序数组第一个</p> <p>适合场景：每个元素距离其最终位置不远时，我们选择插入排序。</p> <ol> <li>首先把10当成有序数组的最后一位，20当成无序数组的第一位，20和10比较，20比10大不移动。</li> <li>之后用无序数组向后移动一位，变成3，3和20比较，比20小，把3放10和20中间，在用3和10比，比10小，放10前面。</li> <li>此时有序最后一位仍是20，用8再去和前面几位有序数组进行比较，一次循环遍历！</li> </ol> <pre> <code class="language-cpp">void InsertSort(int arr[],int nLength) { int j;//有序数组的最后位置 int i;//无序数组的第一个 int temp; if(arr == NULL || nLength <=0)return; for(i = 1;i<nLength;i++) { j = i-1; temp = arr[i]; //保存无序数组的第一个 //进行比较 while(temp < arr[j] && j >=0) { //将前一个元素向后移动 arr[j+1] = arr[j]; j--; } //将元素放入其对应位置 arr[j+1] = temp; } }</code></pre> <h2><strong>快排</strong></h2> <p>快排的优点：是 <strong>比较次数最少</strong> 的排序！</p> <h3><strong>挖坑填补法</strong></h3> <p>例如数组： <strong> <em>7</em> </strong> ，2，8，4，3，5。我们用temp标记7</p> <ol> <li>我们将第一数7当标准值，此时相当于7是一个坑（用粗斜体标记），然后我们从后面依次找比标准值7小的数，<br> 第一个5就比7小，我们将5放到7的坑里。数组变成5，2，8，4，3， <strong> <em>7</em> </strong> ，这是坑变成最后位数！</li> <li>然后我们在前面找一个比标准值大的数，第3个数8比标准值大，这是我们将8填到数7的坑里！这是数组变成了：<br> 5，2， <strong> <em>7</em> </strong> ，4，3，8，我们对已经操作的数，不再进行考虑比较！</li> <li>这时我们在从前面开始找一个数比标准值小的数3，填坑。数组变成了：2，3，4， <strong> <em>7</em> </strong> ，8，此时前面和后面的数，<br> 皆比标准值小和大！</li> <li>标准值前面的数我们看做一个区域，标准值后面的数我们看成一个区域。依次递归循环此区域。</li> </ol> <pre> <code class="language-cpp">//挖坑填补法 int Sort(int arr[],int nLow,int nHigh) { int temp ; temp = arr[nLow]; //保存标准值 while(nLow < nHigh) { //从后向前找比标准值小的 while( nLow < nHigh) { if(arr[nHigh] > temp) { nHigh--; } //小的放前面 else { arr[nLow] = arr[nHigh]; nLow++; break; } } //从前往后找比标准值大的 while( nLow < nHigh) { if(arr[nLow] < temp) { nLow++; } //大的放后面 else { arr[nHigh] = arr[nLow]; nHigh--; break; } } } //填坑 arr[nLow] = temp; return nLow; } void QuickSort(int arr[],int nLow,int nHigh) { int nIndex; if(arr == NULL )return; if(nLow < nHigh) { //找到标准值位置 nIndex = Sort(arr,nLow,nHigh); //根据标准值将当前数组分割成两部分 Sort(arr,nLow,nIndex-1); Sort(arr,nIndex+1,nHigh); } }</code></pre> <h3><strong>区间（域）分割法</strong></h3> <p>快排的一种，比挖坑填补法快！类似与挖坑填补法，是其优化升级版吧！</p> <p>例如，数组：7，5，4，3，6</p> <ol> <li>我们选最后一个数6作为标准值，有两个标记，一个是循环标记I，一个是区域标记s。s= i - 1<br> s用红体标记，i用粗斜体标记！s， <strong> <em>7</em> </strong> ，5，4，3，6</li> <li>用数6去和第一个数7比较，比标准值大， <strong> 7 </strong> , <strong> <em>5</em> </strong> ,4，3，6，则将遍历元素移动到下一处，比标准值6小，<br> 则将数5和7交换， <strong> 5 </strong> ， <strong>7</strong> ，4，3，6。</li> <li>将遍历指针指下一处， <strong> 5 </strong> ，7， <strong>4</strong> ，3，6，比标准值小，将4和第二个数交换。5， <strong> 4 </strong> ， <strong>7</strong> ，3，6<br> 移动遍历指针，5， <strong> 4 </strong> ，7， <strong>3</strong> ，6</li> <li>比标准值小，将3和第三个数交换。5，4， <strong> 3 </strong> ， <strong>7</strong> ，6，移动遍历指针。5，4， <strong> 3 </strong> ，7， <strong>6</strong></li> <li>这时遍历结束，判断++s与i是否相等，若不等，5，4，3， <strong> 7 </strong> ， <strong>6</strong> ，数组[s]与数组[i]交换。</li> <li>5，4，3， <strong> 6 </strong> ， <strong>7</strong> ，此时标准值6前小后大，递归遍历！</li> </ol> <pre> <code class="language-cpp">//区间分割法 int Sort(int arr[],int nLow,int nHigh) { int nSmall;//小区间的右边界 nSmall = nLow-1; for(nLow;nLow < nHigh;nLow++) { //和标准值进行比较 if(arr[nLow] < arr[nHigh]) { //扩张小区间 if(++nSmall != nLow) { arr[nSmall] = arr[nSmall] ^ arr[nLow]; arr[nLow] = arr[nSmall] ^ arr[nLow]; arr[nSmall] = arr[nSmall] ^ arr[nLow]; } } } //标准值放入对应位置 if(++nSmall != nHigh) { arr[nSmall] = arr[nHigh] ^ arr[nSmall]; arr[nHigh] = arr[nHigh] ^ arr[nSmall]; arr[nSmall] = arr[nHigh] ^ arr[nSmall]; } return nSmall; } void QuickSort(int arr[],int nLow,int nHigh) { int nIndex; if(arr == NULL )return; if(nLow < nHigh) { //找到标准值位置 nIndex = Sort(arr,nLow,nHigh); //根据标准值将当前数组分割成两部分 QuickSort(arr,nLow,nIndex-1); QuickSort(arr,nIndex+1,nHigh); } }</code></pre> <h3><strong>快排区间分割优化</strong></h3> <p>若我们选择的标准值恰好是最小值或者最大值，这是快排发生交换的次数最多，如果我们在选择下标的时候进行优化，</p> <p>我们用随机数选择3个下标，之后选其中位数，会最大限度的减少极值下标的可能！</p> <pre> <code class="language-cpp">//找中间值下标 int GetIndex(int arr[],int nLow,int nHigh) { int a,b,c; srand(time(NULL)); //随机出三个在下标范围之内的下标 a = rand()%(nHigh-nLow+1) + nLow; b = rand()%(nHigh-nLow+1) + nLow; c = rand()%(nHigh-nLow+1) + nLow; //找到三个的中间值 if(arr[a] > arr[b]) { if(arr[b] > arr[c]) return b; else { if(arr[a] < arr[c]) return a; else return c; } } else { if(arr[a] > arr[c]) return a; else { if(arr[b] < arr[c]) return b; else return c; } } } //区间分割法 int Sort(int arr[],int nLow,int nHigh) { int nSmall;//小区间的右边界 int nIndex; nSmall = nLow-1; //降低标准值是最大最小值得概率 nIndex = GetIndex(arr,nLow,nHigh); if(nIndex != nHigh) { arr[nIndex] = arr[nIndex] ^ arr[nHigh]; arr[nHigh] = arr[nIndex] ^ arr[nHigh]; arr[nIndex] = arr[nIndex] ^ arr[nHigh]; } for(nLow;nLow < nHigh;nLow++) { //和标准值进行比较 if(arr[nLow] < arr[nHigh]) { //扩张小区间 if(++nSmall != nLow) { arr[nSmall] = arr[nSmall] ^ arr[nLow]; arr[nLow] = arr[nSmall] ^ arr[nLow]; arr[nSmall] = arr[nSmall] ^ arr[nLow]; } } } //标准值放入对应位置 if(++nSmall != nHigh) { arr[nSmall] = arr[nHigh] ^ arr[nSmall]; arr[nHigh] = arr[nHigh] ^ arr[nSmall]; arr[nSmall] = arr[nHigh] ^ arr[nSmall]; } return nSmall; } void QuickSort(int arr[],int nLow,int nHigh) { int nIndex; if(arr == NULL )return; if(nLow < nHigh) { //找到标准值位置 nIndex = Sort(arr,nLow,nHigh); //根据标准值将当前数组分割成两部分 QuickSort(arr,nLow,nIndex-1); QuickSort(arr,nIndex+1,nHigh); } }</code></pre> <h3><strong>快排终极优化</strong></h3> <p>如果数量过少时，直接采用插入排序！</p> <h2><strong>CountSort计数排序</strong></h2> <p>基于 <strong>非比较</strong> 排序</p> <p>适用场景：数据分配非常密集的时候！</p> <p>例如数组：2，1，3，1，2，2，3，4</p> <ol> <li>首先在数组中找到最大值和最小值。</li> <li>然后申请一个max-min+1的数组空间。</li> <li>遍历数组，如第一个数2，就在申请的数组空间下标为2-最小值的位置+1。<br> 相当于在申请的数组第2个位置，计数加一，每次遇到相同的值都加一。</li> <li>相当于在申请的数组空间对应下标对应着参数数组中的值，记录其出现的次数。</li> <li>遍历申请的数组空间，对应着下标将值依次存入参数数组。</li> </ol> <pre> <code class="language-cpp">void CountSort(int arr[],int nLength) { int *pCount = NULL; int i; int j; int nMin,nMax; if(arr == NULL || nLength <=0)return; //找最大值和最小值 nMax = arr[0]; nMin = arr[0]; for(i = 1;i<nLength;i++) { if(arr[i] > nMax) { nMax = arr[i]; } if(arr[i] < nMin) { nMin = arr[i]; } } //开辟计数数组 pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1)); memset(pCount,0,sizeof(int ) * (nMax-nMin+1)); //计数 for(i = 0;i<nLength;i++) { pCount[arr[i]-nMin]++; } //放回原数组 j = 0; for(i = 0;i< nMax-nMin+1;i++) { while(pCount[i] != 0) { arr[j] = i+nMin; j++; pCount[i]--; } } }</code></pre> <h2><strong>ShellSort希尔排序</strong></h2> <p>插入排序的优化，按步长进行分组，然后在组内进行插入排序，然后在二分法步长，重复此过程。（ps:不一定要二分步长）</p> <p>使用场景：数据少的时候！</p> <p>例如：35，5，9，12，21，8，7，4，13，25，21，14，长度，n</p> <ol> <li>第一次：$ gap=\displaystyle\frac{n}{2}=6 $，也就是说差6为一组，35和7一组，5和4，9和13，12和25，21和21，8和14。<br> 每组内进行插入排序，所以35和7互换位置，5和3互换位置。数组：7，4，9，12，21，8，33，5，13，25，21，14</li> <li>第二次：$ gap=\displaystyle\frac{gap}{2}=3 $，差3为一组，7，12，33，25一组，4，21，5，21一组，9，8，13，14一组。每组内进行插入排序，25和33换，31和5换。数组：7，4，8，12，5，9，25，21，13，33，21，14</li> <li>第三次：$ gap=\displaystyle\frac{gap}{2}=1 $向下取整。所以直接对整个数组进行一次插入排序。</li> <li>总结：每次进行组内的插入排序，都是为了让元素距其最终位置更近一步！</li> </ol> <pre> <code class="language-cpp">void ShellSort(int arr[],int nLength) { int gap; int i; //小组 int j;//插入排序 int k; int temp;//保存无序数组的第一个 if(arr == NULL || nLength <=0)return; //定步长 for(gap = nLength/2 ; gap >0 ; gap/=2) { //按照步长分组 for(i = 0;i<gap;i++) { //各组内部插入排序 for(j = i+gap;j<nLength;j+=gap) { k = j - gap; //有序数组的最后一个 temp = arr[j]; //无序数组的第一个 while(arr[k] > temp && k >=i) { arr[k +gap] = arr[k]; k-=gap; } arr[k+gap] = temp; } } } }</code></pre> <h3><strong>希尔排序的优化</strong></h3> <p>分组时，让各组一起进行插入排序，都只进行一次，然后循环进行，代码看起来简洁，但是实际耗时基本相同！</p> <pre> <code class="language-cpp">void ShellSort2(int arr[],int nLength) { int gap; int i; //小组 int j;//插入排序 int k; int temp;//保存无序数组的第一个 if(arr == NULL || nLength <=0)return; //定步长 for(gap = nLength/2 ; gap >0 ; gap/=2) { for(i = gap;i<nLength;i++) { //各组内部插入排序 k = i - gap; //有序数组的最后一个 temp = arr[i]; //无序数组的第一个 while(arr[k] > temp && k >=0) { arr[k +gap] = arr[k]; k-=gap; } arr[k+gap] = temp; } } }</code></pre> <h2><strong>MergeSort归并排序</strong></h2> <p>先拆分再合并。有2路，3路，5路等，这里用2路作为举例说明。先将数组按照二分法（2路）进行递归拆分，</p> <p>拆分到每个块里只剩一个元素，然后和相邻元素进行比较排序合并，在比较在合并。</p> <h3>流程</h3> <p><img src="https://simg.open-open.com/show/cee70d84cc3ad6132896fd36eff1baac.jpg"></p> <p> </p> <pre> <code class="language-cpp">void Merge(int arr[],int nLow,int nHigh) { int nBegin1; int nEnd1; int nBegin2; int nEnd2; int *pTemp = NULL; int i; nBegin1 = nLow; nEnd1 = (nLow+nHigh)/2; nBegin2 = nEnd1+1; nEnd2 = nHigh; pTemp = (int *)malloc(sizeof(int ) *(nHigh-nLow+1)); //合并 i = 0; while(nBegin1 <=nEnd1 && nBegin2 <= nEnd2) { if(arr[nBegin1] < arr[nBegin2]) { pTemp[i] = arr[nBegin1]; nBegin1++; } else { pTemp[i] = arr[nBegin2]; nBegin2++; } i++; } //将有剩余的数组元素放入临时数组 while(nBegin1 <= nEnd1) { pTemp[i] = arr[nBegin1]; i++; nBegin1++; } while(nBegin2 <= nEnd2) { pTemp[i] = arr[nBegin2]; i++; nBegin2++; } //将临时数组元素放回原数组 for(i = 0;i < nHigh-nLow +1;i++ ) { arr[i+nLow] = pTemp[i]; } //释放 free(pTemp); pTemp = NULL; } void MergeSort(int arr[],int nLow,int nHigh) { int nMid; if(arr == NULL )return; //两路归并 nMid = (nLow + nHigh)/2; if(nLow < nHigh) { //先拆分 MergeSort(arr,nLow,nMid); MergeSort(arr,nMid+1,nHigh); //合并 Merge(arr,nLow,nHigh); } }</code></pre> <h2><strong>HeapSort堆排序</strong></h2> <p>堆排序是顺序储存，分为大根堆（大堆）和小根堆（小堆）。</p> <p>大堆：父亲结点一定是三个结点最大的！</p> <p>小堆：父亲结点一定是三个结点最小的！</p> <p>并且左右儿子结点并没有什么大小顺序关系，我们只是把这个顺序存储的结构看作是二叉树的结构，</p> <p>我们仅仅是看作二叉树的形式，实际上也是在数组进行操作，并且根据完全 二叉树性质(第5条) 来进行排序，对此我们要先掌握二叉树的基本知识。</p> <p>适用场景：在n个元素里找前几个最大的或最小的，我们用堆，并且找大的用小堆，找小的用大堆。</p> <p>例如：一个数组｛10，2，7，4，6，12，11，9，8｝</p> <p><img src="https://simg.open-open.com/show/7292e124d8ec77774f6e9681a9dcef9c.jpg"></p> <ol> <li>首先数组按照二叉树的形势，我们只是按照二叉树对应的性质来将数组假想成二叉树的样子（并没有真正的改变数组的结构）。</li> <li>我们按照图2的方式，从下往上从右往左的调整结点的位置，使其遵循大堆的特点！</li> <li>图三是我们第一次调整好成大堆的样子。</li> <li>图四我们将堆顶和数组最后一个元素对换。</li> <li>然后重新按照前面的步骤调整成大堆，最后我们二叉树的第一个结点就是最大的数，依次类推。 二叉树链接</li> </ol> <h3><strong>堆排序类型题</strong></h3> <p>类型题小结：</p> <ol> <li>在一个数组中找出前4个最大的数？<br> 答：首先我们想到的是用小堆，我们建立一个只有四个结点的小堆(图在下面)，将数组元素一次放入小堆，并调整成小堆，这是用数组第五元素和堆顶元素比较，若比堆顶元素大的话，则把堆顶元素放入小堆，并移走小堆的最后一个元素（左边最下面），循环完数组小堆里的数就是前4大的！</li> <li>在50亿个数里找出前50大？<br> 答：还是用小堆，建50个结点，将数据根据内存容量分流，依次按流通过小堆，每个流里选出前50大的，最后在整合到一起，在选出前50的数？</li> <li>在一个数据流中找到中位数？数据流：一直不间断提供数据，随时提供，不是一个固定的数组。<br> 建立一个大堆和小堆，将数据丢入大堆，并且调整大堆，把大堆堆顶扔小堆里，当来数据的时候，调整小堆，把小堆堆顶放大堆里，来数据时，放入大堆并调整大堆，把大堆堆顶放入小堆里。依次循环过程。此时，小堆堆顶是较大数里最小的，大堆堆顶是比较小数里最大的。若数据的个数为奇数时，小堆堆顶是其中位数。当数据的个数为偶数时，小堆堆顶和大堆堆顶的和除2是其中位数。</li> </ol> <p style="text-align:center"><img src="https://simg.open-open.com/show/4c5b686a01a5370f53b7a8df0a7a1a14.jpg"></p> <h3><strong>堆排序代码</strong></h3> <pre> <code class="language-cpp">#define nLeft nRootID*2+1 #define nRight nRootID*2+2 void Adjust2(int arr[],int nLength,int nRootID) { int nMax; //在有孩子的情况下 假设左孩子是大的 for(nMax = nLeft;nLeft < nLength;nMax = nLeft /*下一次继续假设左孩子是最大的8*/) { //两个孩子 if(nRight < nLength) { //右孩子大 if(arr[nMax] < arr[nRight]) { nMax = nRight; } } //大的 和父亲比较 大 则交换 if(arr[nMax] > arr[nRootID]) { arr[nMax] = arr[nRootID] ^ arr[nMax]; arr[nRootID] = arr[nRootID] ^ arr[nMax]; arr[nMax] = arr[nRootID] ^ arr[nMax]; nRootID = nMax; } else { break; } } } void HeapSort(int arr[],int nLength) { int i; if(arr == NULL || nLength <=0)return; //建初始堆 for(i = nLength/2-1;i>=0;i--) { Adjust2(arr,nLength,i); } //排序 for(i = nLength-1;i>0;i--) { //最大值放后面 arr[i] = arr[i] ^ arr[0]; arr[0] = arr[i] ^ arr[0]; arr[i] = arr[i] ^ arr[0]; //调整根节点 Adjust2(arr,i,0); } }</code></pre> <p> </p> <p>来自：http://www.jianshu.com/p/a1bfc6114022</p> <p> </p>