当前位置：首页 > 范文大全 > 工作总结>排序算法总结

排序算法总结

2023-05-10 08:05:15 收藏本文下载本文

“abc123”通过精心收集，向本站投稿了15篇排序算法总结，下面是小编给大家带来关于排序算法总结，一起来看看吧，希望对您有所帮助。

排序算法总结

篇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

迭代方式实现

运行结果:

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入门教程超详细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

【排序算法总结】相关文章：

1.选择排序算法总结

2.笔试中各种排序算法的复杂度

3.python计数排序和基数排序算法实例