在程序设计语言中，排序算法主要有冒泡排序、快速排序、选择排序以及计数排序等1。

冒泡排序（Bubble Sort）是最简单和最通用的排序方法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序2。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，于是将这种排序算法形象地称为冒泡排序3。

算法原理

假定序列中有n个数，要进行从小到大的排序。若参与排序的数组元素共有n个，则需要n-1轮排序。在第í轮排序中，从左端开始，相邻两数比较大小，若反序则将两者交换位置，直到比较第n+1-i个数为止。第1个数与第2个数比较，第2个数和第3个数比较，一直到第n-i个数与第n+1-i个数比较，一共处理 n-i次。此时，第n+1-i个位置上的数已经有序，后续就不需要参加以后的排序。4

（1）第1轮冒泡排序先从第1个数和第2个数开始比较，若第1个数大于第2个数，则需要交换两者的位置；否则保持不变。重复这一过程，直到处理完本轮数列中最后两个数。4

（2）第2轮冒泡排序与第1轮冒泡排序进行相同的排序，使大的数交换到n-2的位置上。4

（3）重复以上过程，共需经过n-1轮冒泡排序后，数据实现升序排序。4

算法示例

对于序列[26，28，24，11]，采用非递减规则进行排序，排序过程如下所示。

(1) 比较相邻的元素。如果第一个比第二个大，就交换他们两个。5

(2) 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。5

(3) 针对所有的元素重复以上的步骤，除了最后一个。5

(4) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。5

算法分析

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 和记录移动次数 均达到最小值5：

， 。

所以，冒泡排序最好的时间复杂度为 。5

若初始文件是反序的，需要进行 趟排序。每趟排序要进行 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：5

冒泡排序的最坏时间复杂度为 。5

综上，因此冒泡排序总的平均时间复杂度为 。5

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。5

算法实现

C语言

<pre data-lang="cpp">void bubble_sort(int* arr, int len)  {      int i, j;      for (i = 0; i < len; i++)          for (j = 1; j < len - i; j++)              if (arr[j - 1] > arr[j])                  swap(arr[j - 1], arr[j]);  }

Visual Fox Pro语言

<pre data-lang="bash">?'Original Array ' + CHR(43147)DIMENSION arr(10)FOR i = 1 TO 10    arr(i) = ROUND(rand()*100,0)ENDFORDISPLAY MEMORY LIKE arr?'After Sort ' + CHR(43147)FOR i = 1 TO 10    FOR j = 1 TO 10 - i        IF arr(j) > arr(j + 1)            lnTemp = arr(j)            arr(j) = arr(j + 1)            arr(j + 1) = lnTemp        ENDIF    ENDFORENDFORDISPLAY MEMORY LIKE arr

Python3

<pre data-lang="python">def bubble_sort(nums):    for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数        for j in range(len(nums) - i - 1):  # j为列表下标            if nums[j] > nums[j + 1]:                nums[j], nums[j + 1] = nums[j + 1], nums[j]    return numsprint(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))# 输出：[8, 12, 19, 22, 32, 33, 45, 97]

Swift

<pre data-lang="js">func bubbleSort(_ nums: inout [Int]) {    let n = nums.count    for i in 0..<n {        for j in 0..<(n - 1 - i) {            if nums[j] > nums[j + 1] {                nums.swapAt(j, j + 1)            }        }    }    print(nums)}var nums = [1,3,7,8,9]bubbleSort(&nums)

C++

C++语言程序示例如下

<pre data-lang="cf">#include <iostream>using namespace std;template<typename T>//整数或浮点数皆可使用void bubble_sort(T arr[], int len){    int i, j;  T temp;    for (i = 0; i < len - 1; i++)        for (j = 0; j < len - 1 - i; j++)        if (arr[j] > arr[j + 1])        {            temp = arr[j];            arr[j] = arr[j + 1];            arr[j + 1] = temp;        }}int main(){    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };    int len = (int) sizeof(arr) / sizeof(*arr);    bubble_sort(arr, len);    for (int i = 0; i < len; i++)        cout << arr[i] << ' ';    cout << endl;    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };    len = (int) sizeof(arrf) / sizeof(*arrf);    bubble_sort(arrf, len);    for (int i = 0; i < len; i++)        cout << arrf[i] << ' ';    return 0;}

RUBY

<pre data-lang="ruby">def bubbleSort(array)    return array if array.size < 2    (array.size - 2).downto(0) do |i|        (0 .. i).each do |j|            array[j], array[j + 1] = array[j + 1], array[j] if array[j] >= array[j + 1]        end    end    return arrayend

PHP

<pre data-lang="php">function bubbleSort($numbers) {    $cnt = count($numbers);    for ($i = 0; $i < $cnt - 1; $i++) {        for ($j = 0; $j < $cnt - $i - 1; $j++) {            if ($numbers[$j] > $numbers[$j + 1]) {                $temp = $numbers[$j];                $numbers[$j] = $numbers[$j + 1];                $numbers[$j + 1] = $temp;            }        }    }    return $numbers;}$num = array(20, 40, 60, 80, 30, 70, 90, 10, 50, 0);var_dump(bubbleSort($num));//输出结果如下：//array(10) {//  [0]=>//  int(0)//  [1]=>//  int(10)//  [2]=>//  int(20)//  [3]=>//  int(30)//  [4]=>//  int(40)//  [5]=>//  int(50)//  [6]=>//  int(60)//  [7]=>//  int(70)//  [8]=>//  int(80)//  [9]=>//  int(90)//}

C#语言

<pre data-lang="c#">冒泡算法C#namespace 数组排序{    class Program    {        static void Main(string[] args)        {            int temp = 0;            int[] arr = {23, 44, 66, 76, 98, 11, 3, 9, 7};            #region该段与排序无关            Console.WriteLine("排序前的数组：");            foreach (int item in arr)            {                Console.Write(item + "");            }            Console.WriteLine();            #endregion            for (int i = 0; i < arr.Length - 1; i++)            {                #region将大的数字移到数组的arr.Length-1-i                for (int j = 0; j < arr.Length - 1 - i; j++)                {                    if (arr[j] > arr[j + 1])                    {                        temp = arr[j + 1];                        arr[j + 1] = arr[j];                        arr[j] = temp;                    }                }            #endregion            }            Console.WriteLine("排序后的数组：");            foreach (int item in arr)            {                Console.Write(item+"");            }            Console.WriteLine();            Console.ReadKey();        }    }}

Erlang

<pre data-lang="erlang">bubble_sort(L)->bubble_sort(L,length(L)).bubble_sort(L,0)->L;bubble_sort(L,N)->bubble_sort(do_bubble_sort(L),N-1).do_bubble_sort([A])->[A];do_bubble_sort([A,B|R])->caseA<Boftrue->[A|do_bubble_sort([B|R])];false->[B|do_bubble_sort([A|R])]end.

JAVA

<pre data-lang="clike">    public static void bubbleSort(int arr[]) { int temp;//临时变量        for(int i =0 ; i<arr.length-1 ; i++) {                       for(int j=0 ; j<arr.length-1-i ; j++) {                  if(arr[j]>arr[j+1]) {                    temp = arr[j];                                        arr[j]=arr[j+1];                                        arr[j+1]=temp;            }            }            }    }

Kotlin

<pre data-lang="java">fun bubbleSort(array: Array<Int>) {    val arrayLength = array.size       for (i in 0 until arrayLength) {               for (j in 0 until arrayLength - i - 1) {                       if (array[j] > array[j + 1]) {                               val temp = array[j]                               array[j] = array[j + 1]                               array[j + 1] = temp                      }              }      }      // Prints result.}

JavaScript

<pre data-lang="xml">function bubbleSort(arr) {    var i = arr.length, j;    var tempExchangVal;    while (i > 0) {        for (j = 0; j < i - 1; j++) {            if (arr[j] > arr[j + 1]) {                tempExchangVal = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = tempExchangVal;            }        }        i--;    }    return arr;}var arr = [3, 2, 4, 9, 1, 5, 7, 6, 8];var arrSorted = bubbleSort(arr);console.log(arrSorted);alert(arrSorted);

控制台将输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

并且弹窗；

Visual Basic语言

<pre data-lang="vb">Sub maopao()    Dim a = Array(233, 10086, 31, 15, 213, 5201314)    Dim i As Integer, j As Integer        For i = UBound(a) - 1 To 0 Step -1        For j = 0 To i            If a(j) > a(j + 1) Then                a(j) = a(j) + a(j + 1)                a(j + 1) = a(j) - a(j + 1)                a(j) = a(j) - a(j + 1)            End If        Next j    Next i    For i = 0 To UBound(a)        Print a(i)    Next iEnd Sub

Objective-C

<pre data-lang="cpp"> for (int i = 0; i<result.count-1; i++) {        for (int j = 0; j<result.count-1-i; j++) {            NSInteger left = [result[j] integerValue];            NSInteger right = [result[j+1] integerValue];            if (left>right) {                [result exchangeObjectAtIndex:j withObjectAtIndex:j+1];            }        }    }NSLog(@"%@",result);

Go语言

<pre data-lang="python">package mainimport (    "fmt")const (    LENGTH = 8)func main() {    var tmp int    number := []int{95, 45, 15, 78, 84, 51, 24, 12}    for i := 0; i < LENGTH; i++ {        for j := LENGTH - 1; j > i; j-- {            if number[j] < number[j-1] {                tmp = number[j-1]                number[j-1] = number[j]                number[j] = tmp            }        }    }    for i := 0; i < LENGTH; i++ {        fmt.Printf("%d ", number[i])    }    fmt.Printf("\n")}

GO语言2

<pre data-lang="python">func BubbleSort(values []int) {    flag := true    vLen := len(values)    for i := 0; i < vLen-1; i++ {        flag = true        for j := 0; j < vLen-i-1; j++ {            if values[j] > values[j+1] {                values[j], values[j+1] = values[j+1], values[j]                flag = false                continue            }        }        if flag {            break        }    }}

PASCAL

<pre data-lang="cpp">var    a:array[1..4] of integer;    i, j, temp, n:integer;begin   read(n);   for i := 1 to n do read(a[i]);   for i := 1 to n do       for j := 1 to n-i do           if a[j] > a[j + 1] then               begin                   temp := a[j];                   a[j] := a[j + 1];                   a[j+1] := temp;               end;    for i:= 1 to n do write(a[i]);end.

Python

<pre data-lang="python">def bubble(bubbleList):    listLength = len(bubbleList)    while listLength > 0:        for i in range(listLength - 1):            if bubbleList[i] > bubbleList[i+1]:                bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]        listLength -= 1    print bubbleListif __name__ == '__main__':    bubbleList = [3, 4, 1, 2, 5, 8, 0]    bubble(bubbleList)

汇编

<pre data-lang="python">有一个首地址为A的5个有符号数字的数组，请采用“冒泡”排序DATAS SEGMENTA  DW 9,4,26,85,38DATAS ENDSCODES SEGMENTASSUME CS:CODES,DS:DATASSTART:    MOV AX,DATAS    MOV DS,AX    MOV DI,4;初始化外循环次数为数组个数-1 LP1:MOV CX,DI;外循环次数初值为数组个数-1     MOV  BX,0;基址初值BX为0  LP2:MOV AX,A[BX]    CMP AX,A[BX+2]    JGE CONT;大于等于不交换    XCHG AX,A[BX+2];小于交换,AX保存的为较大的数MOV A[BX],AX;A[BX]保存的为较大的数，准备进行下一次比较,  CONT:ADD BX,2;基址初值BX+2,字变量，下一个字偏移地址+2LOOP LP2  ;内循环次数-1,内循环次数是否为0？    DEC DI;外循环次数-1    JNZ LP1;外循环次数是否为0?    MOV AH,4CH    INT 21HCODES ENDS    END START

lua

<pre data-lang="cpp">function sortBubble(list)    local len = #list    for i = 1, len do        for j = 1, len-i do            if list[j+1]>list[j] then                local t = list[j+1]                list[j+1] = list[j]                list[j] = t            end        end    endend

算法改进

标志法

对于序列[1，2，3，5，4]，在第1轮冒泡排序后，序列仍为[1，2，3，4，5]，进而发现后续3轮中都没有发生数据交换，即其实不用再执行后面的几轮。算法只需要执行到某轮排序不需要交换数据即可。4

在原来的程序中，加上一个标志变量flag，用于记录在这一趟排序中是否发生了数交换。如果某轮结束后flag的值为False，则说明本轮没有交换行为，数据已经全部有序，可以提前结束排序，具体如下。4

（1）在第1轮冒泡排序中首先比较第1个数和第2个数，若前者大于后者，则交换两者位置，同时flag=True；否则不换。重复这一过程，直到处理完最后两个数据。4

（2）如果flag=False，则结束循环；否则重复上述过程。

具体算法如下。4

<pre data-lang="null">flag=Truefor i in range(1,n):flag=Falsefor j in range(0,n-i):if a[j]<a[j+1]:a[j],a[j+1]=a[j+1],a[j]flag=Trueif not flag:break

区间控制法

对于序列[2，3，4，5，9，8，7]，采用“上冒”，并从数组的末尾开始进行排序，则第一轮排序结束后[2，3，4，5，7，9，8]。在第一趟排序中，当7和9交换位置后，后续的数字都没有互换，即在后续的排序中[2，3，4，5]不需要参与排序。得出结论：每轮遍历的区间边界都是由上一轮遍历最后一次发生交换的位置决定的。这样一来，可以引入标记变量last记录每轮排序最后一次交换的位置，并将last赋给下一轮遍历区间的终点。大大缩小了下一轮排序遍历区间，快速收缩待排序范围，从而提高了算法效率。4

例如，序列[2，3，4，5，9，8，7]，排序过程如下所示（“上冒”排序，并且从数组末尾开始比较）。

通过区间控制法，可以快速地结束排序。4

（1）第1轮冒泡排序先比较第n-1个数和第n-2个数，若前者大于后者，则交换两者位置，同时记录最后一次交换的位置last，重复这一过程，直到处理完数组中最后两个元素中的数据。4

（2）下一轮排序从n-1至last，重复上面的过程，直到结束循环。4

具体排序算法如下。4

<pre data-lang="null">i=1while i<n:last=n-1for j in range(n-1,i-1,-1):if a[j]<a[j-1] :a[j],a[j-1]=a[j-1],a[j]last=ji=last+1

算法比较

快速排序与冒泡排序

快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。6

一趟快速排序的具体做法是：假设两个指针low和high设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。6

快速排序的平均时间为O(N*logN)，通常，快速排序被认为是，在所有同数量级O(N*logN)的排序方法中，其平均性能最好。但是，若初始记录序列被关键字有序或基本有序时，快速排序将退化为冒泡排序，其时间复杂度为O(n²)。[9]

各种排序时间复杂度比较

从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储最多。[9]

从方法的稳定性来比较，基数排序是稳定的内排方法，直接插入排序和冒泡排序也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。一般来说，排序过程中的“比较”是在“相邻的两个记录关键字”间进行的排序方法是稳定的。值得提出的是，稳定性是由方法本身决定的，对不稳定的排序方法而言，不管其描述形式如何，总能举出一个说明不稳定的实例来。反之，对稳定的排序方法，总能找到一种不引起不稳定的描述形式。

来源: 百度百科

内容资源由项目单位提供