排序算法总结（精选19篇）由网友“我请你喝果汁”投稿提供，下面是小编收集整理的排序算法总结，供大家参考借鉴，欢迎大家分享。

篇1：选择排序算法总结

这里实现了选择数组里面最小值的代码，读者可以以此类推自己写出选择最大值的算法

/** * 找到最小的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param minNumber 输出最小值 * @return 最小值在数组里面的位置 */size_t findMin(int array[] , int arraySize , int * minNumber){ if(array == NULL || arraySize <= 0 || minNumber == NULL) return -1; int minPos = -1; int minNumberTemp=INT_MAX; for (int i = 0; i < arraySize; ++i) { if(array[i] < minNumberTemp) {minNumberTemp=array[i];minPos = i; } } *minNumber = minNumberTemp; return minPos;}

运行结果：

input array is :

48 18 97 27 13 85 8 38 95 31

find the min number 8 at pos 7

我们从代码里面可以看出for循环运行n次，每次都要进行一次比较if(array[i] < minNumberTemp)，如果我们标记的最小值大于当前的数组元素，就重新标记当前数组元素为最小值。因为这个代码比较简单，这里不再赘述。

选择算法之选取最大数和最小数

条件改变，现在要选择一个序列里面的最大数和最小数，这里和上面讲述过的选择最大数或者最小数有所不同，上面的要做的只是选择最大值或者最小值，而现在我们要同时选择最大值和最小值。

博主第一次看见这个题目时，和只选择最小数的情形一对比，这不是一样的么，只要在循环里面多加一个最大数的比较不就行了？的确是可以，我们来看一下部分代码实现

篇2：选择排序算法总结

/** * 找到最小的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param minNumber 输出最小值 * @return 最小值在数组里面的位置 */MinMaxPair findMinMax(int array[] , int arraySize , int * minNumber , int * maxNumber){ /** 省略了一些代码 */ for (int i = 0; i < arraySize; ++i) { if(array[i] < minNumberTemp) {minNumberTemp=array[i];minPos = i; } if(array[i] >maxNumberTemp) {maxNumberTemp = array[i];maxPos = i; } } /** 省略了一些代码 */}

这里在一个循环里面要进行两次比较，于是运行时间为2n,虽然也是线性时间里面完成选择，但是常数项的开销明显变多了不少

篇3：选择排序算法总结

还记得之前讲过的快速排序_QUICKSORT么，快速选择算法就是运用了快速排序算法的思想,假设我们现在有一数组A[left...right]

1. 首选在数组A里面选取一个主元M

2. 遍历一遍数组(从left到right)，将比主元M大的元素放在主元的右边,小于等于主元的元素放在主元的左边，此时主元在数组中的位置为i。于是主元M就是数组里面的第i个顺序统计量

3. 比较主元位置i和目标顺序统计量k，如果i=k,就直接返回主元M;如果k< nobr=“”>,就更新right=i?1,转到动作(2)继续开始运行;如果k>i,那么就更新left=i+1,k=i?left,转到动作(2)继续开始运行。

就这样我们可以找到第k个目标顺序统计量，该操作的期望运行时间为O(n)

篇4：选择排序算法总结

我们在这里采用两个方法来实现快速选择算法的实现，一个是迭代，一种是递归，两种算法实现的思想都一样，只是实现的方式不同而与

递归方式实现

/** * 找到数组里面第k大的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param kthNumber 第k大元素的大小 * @param k 第k大的元素 */void randomizedSelect(int array[] , int arraySize , int * kthNumber , int k){ if(array == NULL || arraySize <= 0 || kthNumber == NULL || k <0 || k >= arraySize) return; randomizedSelectKernel(array, 0 , arraySize-1 , kthNumber , k);}/** * 找到leftBorder到rightBorder中第k大的元素,递归函数 * @param array 输入的数组 * @param leftBorder 左边界 * @param rightBorder 右边界 * @param kthNumber 第k大的元素的实际值 * @param k 第k大的元素 */void randomizedSelectKernel(int array[], int leftBorder , int rightBorder ,int * kthNumber , int k){ if(leftBorder >rightBorder) return ; // 这里采用快速排序的思想来完成 int i = leftBorder-1; int j = leftBorder; int x = array[rightBorder]; // 首先找到主元 for(; j < rightBorder ; ++j) { if(array[j] <= x) {exchange(array , j , ++i); } } ++i; exchange(array , i , rightBorder); // 现在位置i就是需要放置主元的地方 if(i == leftBorder+k-1) *kthNumber = array[i]; else if(i >leftBorder+k-1) randomizedSelectKernel(array , leftBorder , i-1 , kthNumber , k); else if(i < leftBorder+k-1) randomizedSelectKernel(array , i+1, rightBorder , kthNumber , k-(i-leftBorder+1));}

运行结果

input array is :

96 47 95 38 53 45 3 92 20 73

2th max number is———————- 20

3 20 45 38 47 53 73 92 96 95

1th max number is———————- 3

3 20 45 38 47 53 73 92 96 95

3th max number is———————- 38

3 20 38 45 47 53 73 92 96 95

6th max number is———————- 53

3 20 38 45 47 53 73 92 96 95

迭代方式实现

/** * 找到数组里面第k大的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param kthNumber 第k大元素的大小 * @param k 第k大的元素 */void randomizedSelect(int array[] , int arraySize , int * kthNumber , int k){ if(array == NULL || arraySize <= 0 || kthNumber == NULL || k <0 || k >= arraySize) return; int left = 0; int right = arraySize-1; int kTemp = k; while(left <= right) { // 采用快速排序的思想 // 首先找到主元 int i = left-1; int j = left; int x = array[right]; for(; j < right ; ++j) {if(array[j] <= x){ exchange(array , ++i , j);} } ++i; exchange(array , i , right); /** 现在位置i就是主元位置 */ if(i == kTemp+left-1)// 找到第k大的元素 {*kthNumber = array[i];return; } else if (ikTemp+left-1) {right = i-1; } }}

运行结果:

input array is :

62 66 70 54 74 98 83 52 80 19

2th max number is———————- 52

19 52 54 62 74 98 83 70 80 66

1th max number is———————- 19

19 52 54 62 66 98 83 70 80 74

3th max number is———————- 54

19 52 54 62 66 98 83 70 80 74

6th max number is———————- 70

19 52 54 62 66 70 74 98 80 83

篇5：选择排序算法总结

但是对于这个算法我们还是可以进行优化的，我们每次选出两个元素，首先对这两个元素进行对比，将其中小者与标记最小数进行比较，如果小者小于最小数，那么就替换最小数，将其中大者与最大数进行比较，如果大者大于最大数，就替换最大数，这样下来只需要循环n/2遍，每遍比较三次，于是运行时间为3n/2,比没有优化之前的代码节省了25%的运行时间

/***记录最大值和最小值在数组里面的位置*/class MinMaxPair{public: MinMaxPair(int _minPos = -1 , int _maxPos = -1):minPos(_minPos),maxPos(_maxPos){} size_t minPos;// 最小值在数组里面得位置 size_t maxPos;// 最大值在数组里面的位置 bool perator==(const MinMaxPair & pair) { return (this->minPos == pair.minPos && this->maxPos == pair.maxPos); }}; /** 找到一个数组里面的最大值和最小值 */MinMaxPair findMinMax(int array[] , int arraySize , int * minNumber , int * maxNumber){ if(array == NULL || arraySize <= 0 || minNumber == NULL || maxNumber == NULL) return MinMaxPair; /** 奇数个元素设置，取出第一个元素作为初始的最大值和最小值 */ int maxNumberTemp = array[0]; int minNumberTemp = array[0]; size_t maxPos=-1; size_t minPos=-1; int i = 1; if(arraySize%2 == 0)// 一共有偶数个元素，取出前两个元素，大的作为最大值的初始值，小的作为最小值的初始值 { i=2; // 比较数组前两个元素 maxNumberTemp = array[0]; minNumberTemp = array[1]; maxPos = 0; minPos = 1; if(array[0] < array[1]) {maxNumberTemp = array[1];minNumberTemp = array[0];maxPos = 1;minPos = 0; } } for (; i < arraySize ; i+=2) { /** 每次取出两个元素 */ int temp1 = array[i]; int temp2 = array[i+1]; int tempPos1 = i; int tempPos2 = i+1; /** 比较两个取出的元素 */ if(array[i] >array[i+1]) {temp1 = array[i+1];temp2 = array[i];tempPos1 = i+1;tempPos2 = i; } /** 将小者与标识的最小值比较 */ if(minNumberTemp >temp1) {minNumberTemp = temp1;minPos = tempPos1; } /** 将大者与标识的最大值比较 */ if(maxNumberTemp < temp2) {maxNumberTemp = temp2;maxPos = tempPos2; } } // 最后设置输出的元素 *maxNumber = maxNumberTemp; *minNumber = minNumberTemp; return MinMaxPair(minPos , maxPos);}

运行结果

input array is :

69 72 82 53 61 35 43 74 83 76

find the min number 35 at pos 6

find the max number 83 at pos 9

在上面的代码，如果输入数据的长度为奇数，我们就选取第一个元素作为最大值和最小值元素的初始值，并从数组的第二个元素开始每次选出两个元素；如果为偶数，那么取出前两个元素，大的作为最大值的初始值，小的作为最小值的初始值，并从第三个元素开始，每次取出两个元素

快速选择算法

之前讨论的选择最大数和最小数都属于比较极端的情况，要是现在需要选择一个序列里面的第k个顺序统计量呢，有什么比较快速的方法呢？首先想到的就是排序以后再选取啦。不过排序的平均运行时间为O(nlogn),相对于接下来介绍的快速选择算法是慢那么一个级别的。

篇6：选择排序算法总结

/** * 找到数组中的中位数 * @param array 输入的数组 * @param lefyBorder 数组左边界 * @param rightBorder 数组右边界 const int & arraySize = rightBorder - leftBorder+1; * @return 中位数的坐标 */int BFPRT(int array[] , int leftBorder , int rightBorder){ if(array == NULL || leftBorder >rightBorder ) return -1; const int & arraySize = rightBorder - leftBorder +1; // 判断元素的个数是否大于五个 if(arraySize <= 5) { insertSort(array , arraySize); return leftBorder+arraySize/2; } // 如果元素个数大于五个，那么就五五分组 const int & groupSize = 5; int * groupStart=array; int midCount=0; for (int i = leftBorder+groupSize; i <= rightBorder; i+=groupSize) { insertSort(groupStart , groupSize); exchange(array , leftBorder+midCount , i-3 );//将中位数放在数组的最前面 ++midCount; groupStart+=groupSize; } // 剩下的不满五个进行排序 if(arraySize%groupSize != 0) { insertSort(groupStart , arraySize%groupSize); exchange(array , leftBorder+midCount ,leftBorder + arraySize - arraySize%groupSize + (arraySize%groupSize - 1)/2); ++midCount; } // 现在新选出来的所有中位数都在前midCount里面 // 返回中位数的中位数 return BFPRT(array , leftBorder , leftBorder+midCount-1);}/** * 选择第K大的元素 * @param array 输入的数组 * @param leftBorder 左边界 * @param rightBorder 右边界 * @param k 第k个 * @param kthNumber 第k大的数 */void BFPRTselect(int array[] , int leftBorder , int rightBorder ,int k , int * kthNumber){ if(array == NULL || leftBorder >rightBorder || kthNumber == NULL || k >(rightBorder - leftBorder + 1)) return ; /** 选取主元 */ int index = BFPRT(array , leftBorder , rightBorder); if(index == -1) return; cout<<“lefy--->”<”<<<” -=“” 1=“” array=“” else=“” i=“” i-1=“” index=“” int=“” j=“leftBorder;” k=“” k-1=“” kthnumber=“array[i];” leftborder=“” midnumber=“” return=“” rightborder=“” x=“array[rightBorder];”>

运行结果:

before sort the array:

75 84 30 35 77 60 75 32 64 2

lefy—>0 right—>9 index:0 midNumber :75

lefy—>0 right—>6 index:1 midNumber :32

lefy—>0 right—>1 index:1 midNumber :30

2th max number is———————- 30

2 30 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

lefy—>0 right—>1 index:1 midNumber :2

1th max number is———————- 2

2 30 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

3th max number is———————- 32

30 2 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

lefy—>3 right—>9 index:4 midNumber :84

lefy—>3 right—>8 index:4 midNumber :75

lefy—>3 right—>6 index:5 midNumber :35

lefy—>4 right—>6 index:5 midNumber :75

lefy—>4 right—>5 index:5 midNumber :60

lefy—>5 right—>5 index:5 midNumber :64

6th max number is———————- 64

2 30 32 35 60 64 75 75 77 84

after sort the array:

2 30 32 35 60 64 75 75 77 84

注：本文中的所有代码都在这里

<<“>

篇7：选择排序算法总结

细心的读者可能已经发现，我们在一遍一遍对一个数组进行选择的过程中，数据已经慢慢变的有序起来，我们一开始的输入数组为62 66 70 54 74 98 83 52 80 19,在进行了四遍选择以后，发现数组已经被更新为19 52 54 62 66 70 74 98 80 83,接近有序了，

电脑资料

我们知道有序数组对于快速算法是致命的，如果不对快速算法做任何优化，那么快速算法将会达到最差运行时间O(n2)，因为有序的数据将会导致快速排序的分组极度不平衡。

快速选择算法里面也是一样的，应该避免输入有序数组导致的分组极度不平衡的情况，所以我们就做了下面的优化，在进行快速选择之前，首先从数组的头部，中部，尾部选出三个元素出来，找出这三个元素中第二大的元素，并与数组的最后一个元素进行交换，这样我们就可以避免分组极度不平衡的情况了，但是只是能保证避免分组极度不平衡的情况，还是有可能分组不平衡的,下面我们要讲解的BFPRT选择算法可以很好的做到平衡分组

我们在每次迭代或者递归进行之前加上下面的代码

/** 省略了好多代码 */if(leftBorder >rightBorder) return ; // 这里采用快速排序的思想来完成 // 为了避免最差的情况发生 int mid=(leftBorder+rightBorder)/2; int midPos = rightBorder; // mid元素是第二大的 if((array[leftBorder] >array[mid] && array[mid] >array[rightBorder]) ||\ (array[leftBorder] < array[mid] && array[mid] < array[rightBorder]) ) midPos = mid; // left元素是第二大的 else if((array[mid] >array[leftBorder] && array[leftBorder] >array[rightBorder]) ||(array[mid] < array[leftBorder] && array[leftBorder] < array[rightBorder]) ) midPos = leftBorder; if(midPos != rightBorder) exchange(array , midPos , rightBorder); int i = leftBorder-1; int j = leftBorder; /** 省略了好多代码 */

BFPRT选择算法

上面我们讲过，在快速排序算法里面如果主元选择的不合适，将会导致快速排序算法的分组极度不平衡，这样大大降低了快速选择算法的效率

1973 年，Blum、Floyd、Pratt、Rivest、Tarjan一起发布了一篇名为 “Time bounds for selection” 的论文，给出了一种在数组中选出第k大元素平均复杂度为O(n)的算法，俗称“中位数之中位数算法”。这个算法依靠一种精心设计的 pivot 选取方法，即选取中位数的中位数作为主元，从而保证了在最情况下的也能做到线性时间的复杂度，打败了平均O(nlogn)、最坏O(n2)复杂度的快速排序算法

篇8：选择排序算法总结

其实这个算法的最精妙之处在于主元的寻找，该算法可以找到一个主元使得快速排序分组足够平衡

判断元素个数是否大于五个，如果是，就跳转到步骤(2)，否则就对数组进行排序，如果元素个数为奇数，就返回中位数，若为偶数，就返回下中位数 将数组进行分组，每组元素里面的元素各个均为五个，至多有一个数组的元素个数小于五个 将每组元素进行插入排序(元素个数较少的情况下，插入排序性能还是不错的) 把每一组里面的中位数取出来，就是五个元素里面的第三个；对于不满五个元素的组，如果元素个数为奇数，就取中位数，若为偶数，就取下中位数 对取出来的中位数组成一个新的数组，并转到步骤(1),开始对取出来的中位数数组取中位数

vc/QobXE1KrL2KGjPC9wPg0KPGgyIGlkPQ==”bfprt选择算法性能分析“>BFPRT选择算法性能分析

每组五个元素，我们对数组进行分组最后会得到n/5个组。，除去不满五个元素和包括主元x的组，至少有3×(n5?2)≥3n10?6个元素是大于x的，类似的，至少有3n10?6个元素小于x的，于是在每次分组中，两个组最不平衡的情况的也就是7:3,于是得到递归式,这里140是随便选取的一个常数

T(n)={O(1)T(n5)+T(7n10+6)+O(n),n<140,n≥140

计算上式可以得知运行时间为O(n)

篇9：排序算法（一）

进入找工作倒计时状态了，计划好好复习一下数据结构和相关算法，预计用两天时间把见过的排序算法整理下，首先看一下时间复杂度为O（n2）的算法，

首先参考大话数据结构定义一个链表类：

#include#define MAXSIZE 1000 using namespace std; class SqList{ public: SqList:length(0){} SqList(int length1,int value=0):length(length1) { for(int i=0;i=MAXSIZE) { return false; } data[length]=value; length++; } friend ostream& operator<<(ostream& output, SqList list); public: int data[MAXSIZE]; int length; }; void swap(int& a,int &b) { int tmp=a; a=b; b=tmp; } ostream& operator<<(ostream& output, SqList list) { for (int i = 0; i

冒泡排序法：

/** *冒泡排序即相邻的两者相互比较，根据需求把较大的或较小的前移或后移 *记住，两两相邻的比较是冒泡排序的特点之一 */void BubbleSort1(SqList* list){//每次遍历时把较大者后移 int length=list->length; while(length>0) { for(int i=0;idata[i] >list->data[i+1]) swap(list->data[i],list->data[i+1]); } length--; }}void BubbleSort2(SqList* list){//每次遍历时，把较小的前移 for(int i=0;ilength;i++) { for(int j=list->length-2;j>=i;j--) { if(list->data[j] >list->data[j+1]) swap(list->data[j],list->data[j+1]); } } }

选择排序法：

/** *选取排序即每次在未排序队列当中选取一个最小值，然后与第i个值进行交换，直至i为length为止； *当然，也可以选取最大值把到后面，根据需求而定 */void selectSort(SqList* list){ for (int i = 0; i < list->length; ++i) { int min = list->data[i]; int pos = i; for (int j = i+1; j < list->length; ++j) { if (list->data[j] < min) { min = list->data[j]; pos = j; } } if (pos != i) { swap(list->data[i], list->data[pos]); } }}

简单插入排序法：

/** *遍历链表，把每个元素插入到正确位置 */void InsertSort1(SqList *list){ for (int i = 1; i < list->length; ++i) { int j = i - 1; for (; j >=0; j--) { if (list->data[i] >list->data[j]) break; } int tmp = list->data[i]; for (int k = i; k >j+1; --k) { list->data[k] = list->data[k - 1]; } list->data[j + 1] = tmp; }}void InsertSort2(SqList *list){ for (int i = 1; i < list->length; ++i) { if (list->data[i] < list->data[i - 1]) { int tmp = list->data[i]; int j = i-1; for (; j >= 0 && list->data[j] >tmp; --j) {//查找的同时，进行后移操作 list->data[j + 1] = list->data[j]; } list->data[j + 1] = tmp; } }}

希尔排序法（简单插入排序的改进）：

/** *希尔排序是插入排序的一种改进，可以理解为把一个数组分成几个小的数组进行插入排序，再合并使原数组基本有序， *希尔排序一个很关键的步骤是增量的选取，合适的增量能够提高排序效率，但不合适的增量可能会导致程序崩溃或结果错误。 *其次，希尔排序也不是一个稳定的排序算法，因为它是跳跃插入排序的。 *希尔排序只是比前面几种O(n2)的效果稍好，并不会优于后面要提到的快速排序等算法。 */void ShellSort(SqList* list){ int increment = list->length; do{ increment = increment / 3 + 1; for (int i = increment + 1; i < list->length; ++i) { if (list->data[i] < list->data[i - increment]) { int tmp = list->data[i]; int j = i - increment; for (; j >= 0 && list->data[j] >tmp; j -= increment) { list->data[j + increment] = list->data[j]; } list->data[j + increment] = tmp; } } } while (increment >1);}

篇10：python选择排序算法实例总结

作者：pythoner 字体：[增加 减小] 类型：

这篇文章主要介绍了python选择排序算法,以三个实例以不同方法分析了Python实现选择排序的相关技巧,需要的朋友可以参考下

本文实例总结了python选择排序算法，分享给大家供大家参考。具体如下：

代码1：

def ssort(V):#V is the list to be sorted j = 0 #j is the ”current“ ordered position, starting with the first one in the list while j != len(V): #this is the replacing that ends when it reaches the end of the list for i in range(j, len(V)): #here it replaces the minor value that it finds with j positionif V[i] < V[j]: #but it does it for every value minor than position j V[j],V[i] = V[i],V[j] j = j+1 #and here‘s the addiction that limits the verification to only the next values return V

代码2：

def selection_sort(list): l=list[:] # create a copy of the list sorted=[] # this new list will hold the results while len(l): # while there are elements to sort... lowest=l[0] # create a variable to identify lowest for x in l: # and check every item in the list... if x

代码3

a=input(”Enter the length of the list :“)# too ask the user length of the list l=[]# take a emty list for g in range (a):# for append the values from user b=input(”Enter the element :“) # to ask the user to give list values l.append(b) # to append a values in a empty list l print ”The given eliments list is“,l for i in range (len(l)):# to repeat the loop take length of l index=i # to store the values i in string index num=l[i] # to take first value in list and store in num for j in range(i+1,len(l)): # to find out the small value in a list read all values if num>l[j]: # to compare two values which store in num and list index=j# to store the small value of the loop j in index num=l[j]# to store small charecter are value in num tem=l[i] # to swap the list take the temparary list stor list vlaues l[i]=l[index] # to take first value as another l[index]=tem print ”After the swping the list by selection sort is“,l

希望本文所述对大家的Python程序设计有所帮助，

篇11：python实现排序算法

-03-03python局部赋值的规则

-02-02python发布模块的步骤分享

2014-03-03Python 列表(List)操作方法详解

2014-02-02go和python调用其它程序并得到程序输出

2014-04-04python中的实例方法、静态方法、类方法、类变量和实例变量浅析

2014-05-05Python random模块（获取随机数）常用方法和使用例子

-12-12python cookielib 登录人人网的实现代码

-09-09Python httplib，smtplib使用方法

2013-11-11pyramid配置session的方法教程

2014-03-03python实现k均值算法示例(k均值聚类算法)

篇12：python实现排序算法

最近更 新

用python实现的去除win下文本文件头部BOM

Python实现的金山快盘的签到程序

python操作MySQL数据库具体方法

python操作日期和时间的方法

删除目录下相同文件的python代码(逐级优化

python 中的列表解析和生成表达式

Python实例分享：快速查找出被挂马的文件

python列表去重的二种方法

python查找第k小元素代码分享

Python 网络编程说明

热 点 排 行

Python入门教程 超详细1小时学会

python 中文乱码问题深入分析

比较详细Python正则表达式操作指

Python字符串的encode与decode研

Python open读写文件实现脚本

Python enumerate遍历数组示例应

Python 深入理解yield

Python+Django在windows下的开发

python 文件和路径操作函数小结

python 字符串split的用法分享

篇13：排序算法的算法思想和使用场景总结

1. 概述

排序算法是计算机技术中最基本的算法，许多复杂算法都会用到排序。尽管各种排序算法都已被封装成库函数供程序员使用，但了解排序算法的思想和原理，对于编写高质量的软件，显得非常重要。

篇14：排序算法的算法思想和使用场景总结

2. 几个概念

（1）排序稳定：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1，第二个1就是排序前第二个1，第三个1就是排序前的第三个1。同理2也是一样。不稳定就是他们的顺序与开始顺序不一致。

（2）原地排序：指不申请多余的空间进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。

总体上说，排序算法有两种设计思路，一种是基于比较，另一种不是基于比较。《算法导论》一书给出了这样一个证明：“基于比较的算法的最优时间复杂度是O（N lg N）”。对于基于比较的算法，有三种设计思路，分别为：插入排序，交换排序和选择排序。非基于比较的排序算法时间复杂度为O(lg N)，之所以复杂度如此低，是因为它们一般对排序数据有特殊要求。如计数排序要求数据范围不会太大，基数排序要求数据可以分解成多个属性等。

3. 基于比较的排序算法

正如前一节介绍的，基于比较的排序算法有三种设计思路，分别为插入，交换和选择。对于插入排序，主要有直接插入排序，希尔排序；对于交换排序，主要有冒泡排序，快速排序；对于选择排序，主要有简单选择排序，堆排序；其它排序：归并排序。

3.1 插入排序

（1） 直接插入排序

特点：稳定排序，原地排序，时间复杂度O(N*N)

思想：将所有待排序数据分成两个序列，一个是有序序列S，另一个是待排序序列U，初始时，S为空，U为所有数据组成的数列，然后依次将U中的数据插到有序序列S中，直到U变为空。

适用场景：当数据已经基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

（2）希尔排序

特点：非稳定排序，原地排序，时间复杂度O(n^lamda)(1 < lamda < 2), lamda和每次步长选择有关。

思想：增量缩小排序。先将序列按增量划分为元素个数近似的若干组，使用直接插入排序法对每组进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。

适用场景：因为增量初始值不容易选择，所以该算法不常用。

3.2 交换排序

（1）冒泡排序

特点：稳定排序，原地排序，时间复杂度O(N*N)

思想：将整个序列分为无序和有序两个子序列，不断通过交换较大元素至无序子序列首完成排序。

适用场景：同直接插入排序类似

（2）快速排序

特点：不稳定排序，原地排序，时间复杂度O(N*lg N)

思想：不断寻找一个序列的枢轴点，然后分别把小于和大于枢轴点的数据移到枢轴点两边，然后在两边数列中继续这样的操作，直至全部序列排序完成。

适用场景：应用很广泛，差不多各种语言均提供了快排API

3.3 选择排序

（1）简单选择排序

特点：不稳定排序（比如对3 3 2三个数进行排序，第一个3会与2交换），原地排序，时间复杂度O(N*N)

思想：将序列划分为无序和有序两个子序列，寻找无序序列中的最小（大）值和无序序列的首元素交换，有序区扩大一个，循环下去，最终完成全部排序。

适用场景：交换少

（2） 堆排序

特点：非稳定排序，原地排序，时间复杂度O(N*lg N)

思想：小顶堆或者大顶堆

适用场景：不如快排广泛

3.4 其它排序

（1） 归并排序

特点：稳定排序，非原地排序，时间复杂度O(N*N)

思想：首先，将整个序列（共N个元素）看成N个有序子序列，然后依次合并相邻的两个子序列，这样一直下去，直至变成一个整体有序的序列。

适用场景：外部排序

4. 非基于比较的排序算法

非基于比较的'排序算法主要有三种，分别为：基数排序，桶排序和计数排序。这些算法均是针对特殊数据的，不如要求数据分布均匀，数据偏差不会太大。采用的思想均是内存换时间，因而全是非原地排序。

4.1 基数排序

特点：稳定排序，非原地排序，时间复杂度O(N)

思想：把每个数据看成d个属性组成，依次按照d个属性对数据排序（每轮排序可采用计数排序），复杂度为O(d*N)

适用场景：数据明显有几个关键字或者几个属性组成

4.2 桶排序

特点：稳定排序，非原地排序，时间复杂度O(N)

思想：将数据按大小分到若干个桶（比如链表）里面，每个桶内部采用简单排序算法进行排序。

适用场景：0

4.3 计数排序

特点：稳定排序，非原地排序，时间复杂度O(N)

思想：对每个数据出现次数进行技术（用hash方法计数，最简单的hash是数组！），然后从大到小或者从小到大输出每个数据。

使用场景：比基数排序和桶排序广泛得多。

5. 总结

对于基于比较的排序算法，大部分简单排序(直接插入排序，选择排序和冒泡排序)都是稳定排序，选择排序除外；大部分高级排序（除简单排序以外的）都是不稳定排序，归并排序除外，但归并排序需要额外的存储空间。对于非基于比较的排序算法，它们都对数据规律有特殊要求 ，且采用了内存换时间的思想。排序算法如此之多，往往需要根据实际应用选择最适合的排序算法。

篇15：Shell脚本排序算法(冒泡排序)

#/bin/basha=(9 84 51 0 345 1 2 34 1 0) #自己定义一个数组temp=for((i=0;i<10;i++)){ for((j=i;j<10;j++)) { x=${a[$i]} if test $x -ge ${a[$j]} then temp=${a[$i]} a[$i]=${a[$j]} a[$j]=$temp fi }}for((k=0;k<10;k++)){ echo -n ${a[$k]} ” “}echo

上面写的数组是事前在代码里定义好的数组排序，下面的是用户在执行过程中自定义的数组排序，

Shell脚本排序算法(冒泡排序)

，

#/bin/basha=`expr $# + 1`#expr是一个计算操作,$#是参数个数，$#+1是因为$0没有存储参数.temp=for((i=1;i<$a;i++)){ b[$i]=$1 shift 1 }for((i=1;i<$a;i++)){ for((j=i;j<$a;j++)) { x=${b[$i]} if test $x -ge ${b[$j]} then temp=${b[$i]} b[i]=${b[$j]} b[j]=$temp #相当与冒泡排序 fi }}for((k=1;k<$a;k++)){ echo -n ${b[$k]} ” “ #不换行显示}echo$: ./liu.sh 8 7 6 4 100 7

$: 4 6 7 7 8 100

篇16：python 算法 排序实现快速排序

最近更 新

python 实现堆排序算法代码

linux系统使用python监测系统负载脚本分享

python线程池的实现实例

win7安装python生成随机数代码分享

Python Web框架Pylons中使用MongoDB的例子

Python设计模式之单例模式实例

Python 错误和异常小结

python实现猜数字游戏(无重复数字)示例分

Python的print用法示例

python抓取京东商城手机列表url实例代码

热 点 排 行

Python入门教程 超详细1小时学会

python 中文乱码问题深入分析

比较详细Python正则表达式操作指

Python字符串的encode与decode研

Python open读写文件实现脚本

Python enumerate遍历数组示例应

Python 深入理解yield

Python+Django在windows下的开发

python 文件和路径操作函数小结

python 字符串split的用法分享

篇17：图算法之拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序，它使得如果存在一条从vi到vj的路径，那么在排序中Vj出现在Vi后面，一个简单的求拓扑排序的算法是先找出任意一个没有入边的顶点，然后我们显示该顶点，并将它和它的边一起从图中删除。然后为们对图的其余部分应用同样的方法处理。但是这个方法有一点不好，就是每次都要找入度为0的顶点，这种顶点一般很少，如果图很大的话，每次都遍历一遍就浪费很多时间。升级版是先计算每一个顶点的入度，然后将入度为0的顶点存入队列，操作完之后再更新入度。这样就不用遍历整个图而只需要从出队列操作就可以了。下面是代码，队列的操作在上一篇文章中已经实现，只要把类型改成节点的指针即可。

topSort.h

#ifndef __TOPSORT_H#define __TOPSORT_Hstruct graph;struct listNode;typedef struct graph *Graph;typedef struct listNode *Vertex;struct graph{ int numberOfVertex; Vertex *vertexs;};struct listNode{ int indegree; int vertexnumber; Vertex next;};void topSort(Graph G);Graph initinalizeAdjList(int listSize);Graph insertAdjList(Graph G,int pos,int a[],int N);#endif

topSort.c

#include topSort.h#include queue.hvoid topSort(Graph G){ Queue Q; Vertex V,W; int counter=0; int i; Q=createQueue; for(i=1;i<=G->numberOfVertex;i++)//找到入度为0的点，将它们入队列 { if(G->vertexs[i]->indegree==0) EnQueue(G->vertexs[i],Q);} while(!isEmpty(Q))//删除该点，然后将其相邻的点入度减1，再重新检测入队列 { V=DeQueue(Q); printf( %d ,V->vertexnumber); counter++; for(i=1;i<=G->numberOfVertex;i++) { if(isAdj(G->vertexs[i],V)) { if((--G->vertexs[i]->indegree)==0) EnQueue(G->vertexs[i],Q); } } } if(counter!=G->numberOfVertex) { printf(Graph has a cycle); exit(-1); } deleteQueue(Q);}Graph initinalizeAdjList(int listSize)//初始化一个邻接表，就是创建一个指针数组，每个元素只想一个节点{ Graph G; int i; G=(Graph)malloc(sizeof(struct graph)); if(G==NULL) { printf(out of space); exit(-1); } G->numberOfVertex=listSize; G->vertexs=(Vertex*)malloc(sizeof(Vertex)*(listSize+1)); for(i=1;i<=listSize;i++)//这里简单的直接给出节点编号，实际中可以用哈希的方法来获得 { G->vertexs[i]=(Vertex)malloc(sizeof(struct listNode));//初始化节点 G->vertexs[i]->vertexnumber=i; G->vertexs[i]->next=NULL; } return G;}Graph insertAdjList(Graph G,int pos,int a[],int N)//根据给出的数组来给邻接表插入元素{ int j; Vertex v,w; G->vertexs[pos]->indegree=N; w=G->vertexs[pos]; for(j=0;jvertexnumber=a[j]; v->next=NULL; while(w->next) w=w->next; w->next=v; }}int isAdj(Vertex v,Vertex w) //if v adj w判断是不是和目标节点相邻{ Vertex t; t=v->next; while(t) { if(t->vertexnumber==w->vertexnumber) return 1; t=t->next; } return 0;}

main.c

#include queue.h#include topSort.hint main(){ Graph G; int i; int a1[]={2,4,3}; int a2[]={4,5}; int a3[]={6}; int a4[]={6,7,3}; int a5[]={4,7}; int a7[]={6}; G=initinalizeAdjList(7); insertAdjList(G,1,a1,3); insertAdjList(G,2,a2,2); insertAdjList(G,3,a3,1); insertAdjList(G,4,a4,3); insertAdjList(G,5,a5,2); insertAdjList(G,6,a5,0); insertAdjList(G,7,a7,1); for(i=1;i<=7;i++) { Vertex v; v=G->vertexs[i]; while(v) { printf( %d ,v->vertexnumber); v=v->next; } printf(); } topSort(G);}

篇18：PHP简单选择排序算法实例

这篇文章主要介绍了PHP简单选择排序算法实例,本文直接给出实现代码,并以类的方式实现,需要的朋友可以参考下

简单的选择排序算法：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换

代码如下:

<?php

class Sort{

/**

* 简单的选择排序

*

* @param unknown_type $arr

*/

public function selectSort(&$arr) {

$len=count($arr);

for ($i=0;$i<$len;$i++) {

$min=$i;

for ($j=$i+1;$j<=$len-1;$j++) {

if ($arr[$min]>$arr[$j]) {//如果找到比$arr[$min]较小的值，则将该下标赋给$min

$min=$j;

}

}

if ($min!=$i){//若$min不等于$i，说明找到了最小值，则交换

$this->swap($arr[$i],$arr[$min]);

}

}

}

/**

* 将$a和$b两个值进行位置交换

*/

public function swap(&$a,&$b) {

$temp=$a;

$a=$b;

$b=$temp;

}

}

$arr=array(4,6,1,2,9,8,7,3,5);

$test=new Sort();

$test->selectSort($arr);//简单的选择排序

//   var_dump($arr);

?>

简单选择排序的特点：交换移动数据次数相当少，从而节约了相应的时间

简单选择排序的时间复杂度分析：

无论最好最差的情况，其比较次数都是一样多，第i趟排序需要进行n-i次关键字的比较，此时需要比较n(n-1)/2次，

PHP简单选择排序算法实例

，

所以最终的时间复杂度是O(n^2)

尽管与冒泡排序同为O(n^2)，但选择排序的性能还是略优于冒泡排序的。

篇19：算法冒泡排序和快速排序(ObjectC)

冒泡和递归一样，不管大家水平怎么样，基本上都能凑合的写写，快速排序其实主要的也是数据的交换，都算是交换排序，不过快排需要了解分治思想，实现的时候需要递归一下，导致很多时候看快排的时候都看的云里雾里，假设有一个无序的整型数组

索引 0  1  2  3  4   5  6

数值 15 32  8  99 12 17 36，

①取出0位的15作为基准值，然后倒序从后往前找小于15的，将12赋值给0位；

②从前往后找大于15的将32放置到位置4；

③位置1空出来，然后继续倒序找小于15的，正序找大于15的，最后索引到大3的时候重复以上过程。

冒泡排序

冒泡基本上没有什么好说的，直接看代码吧，新建了Sort类处理排序:

//

// Sort.h

// Algorithm

//www.cnblogs.com/xiaofeixiang

// Created by keso on 15/3/15.

// Copyright (c) 2015年 keso. All rights reserved.

//

#import

@interface Sort : NSObject

@property (nonatomic,strong)NSMutableArray *dataSource;

-(void)bubbleSort:(NSMutableArray*)dataSource;

-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end;

@end

Sort.m中的bubbleSort实现:

//冒泡排序

-(void)bubbleSort:(NSMutableArray*)dataSource{

NSUInteger count=[dataSource count];

for(int i=0;i

for (int j=0; j

if ([dataSource[j] intValue]>[dataSource[j+1] intValue]) {

NSString *temp=dataSource[j];

dataSource[j]=dataSource[j+1];

dataSource[j+1]=temp;

}

}

}

for (NSInteger i=0; i<[dataSource count]; i++) {

NSLog(@”排序--%@“,dataSource[i]);

}

}

冒泡排序比较稳定，但是每次只是移动两个数字比较慢，如果是正序的话时间复杂度是O(n)，如果是逆序的需要弄成正序的，那么事件复杂度O(n*n)，会经过n(n-1)/2次比较，平均事件复杂度O(n*n);

快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)，

基本思路如下:

1．先从数组中取出一个数作为基准数值，也可以理解为中间变量。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，也算是出门居家必备的算法了，理解比较好理解，具体的实现能写出来基本上算是理解的，至于更深的就要看工作中实际的操作过程啦。

Sort.h中定义了一个QuickSort方法，还有一个NSMutabArray是为了保存最后的结果的,具体实现:

//快速排序

-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end{

if (start

NSInteger standardValue=[_dataSource[start] intValue];

NSInteger left=start,right=end;

while (start

//从后往前找，如果后面的数值大于基准值，递减

while (startstandardValue) {

end--;

}

//小于基准值的时候，给数组中索引为start赋值

if (start

_dataSource[start]=_dataSource[end];

start=start+1;

}

//从前往后找，如果数值小于基准值，递增

while (start

start++;

}

//大于基准值，给数组中索引为end的数据赋值

if (start

_dataSource[end]=_dataSource[start];

end=end-1;

}

}

//退出的时候值start和end相等

_dataSource[start]=[NSString stringWithFormat:@”%ld“,(long)standardValue];

[self quickSort:left endIndex:end-1];//处理左边

[self quickSort:end+1 endIndex:right];//处理右边

}

}

主函数中的调用如下:

NSMutableArray *data=[[NSMutableArray alloc] initWithObjects:@”10“,@”88“,@”97“,@”33“,@”8“,@”73“,@”18“, nil];

[sort bubbleSort:data];

sort.dataSource=data;

[sort quickSort:0 endIndex:[data count]-1];

for (int i=0; i<[data count]; i++) {

NSLog(@”排序:%@",data[i]);

}

return 0;

代码可能不是最简洁的，但是应该是比较好理解的，如果有问题，随时可以在评论区与我交流~

★ 数据结构课程总结

★ 《递归算法的实现》教学设计

★ 考研计算机专业大纲解析之数据结构

★ 数据结构实验报告

★ 楷书结构教学工作总结

★ 课程学习总结

★ 学习课程的个人总结

★ 计算机二级考试试题

★ 考研计算机专业：基础阶段备考常见问题

★ 机场停机位分配问题研究

《排序算法总结.doc》

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档

【排序算法总结（精选19篇）】相关文章：

计算机二级考试试题及答案2023-06-22

数据结构习题2023-08-06

软件公司个人实习工作日志2023-08-05

算法概念课的教案2022-10-15

信息技术教案高一2022-10-22

腾讯的一道笔试算法题解答2022-10-06

必修三数学知识点高中2022-04-30

高一信息技术教案2022-04-30

腾讯实习生求职笔试面试经历2022-07-26

腾讯实习生笔试经验谈2022-08-07