常见排序算法 [整理]

?

名称复杂度说明备注冒泡排序 BubbleSortO(N*N)

将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮

插入排序 InsertionSortO(N*N)逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置起初，已经排序的元素序列为空选择排序 SelcetionSortO(N*N)首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。
快速排序 QuickSortO(n*log2(n))先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。
堆排序 HeapSortO(n*log2(n))

利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。

近似完全二叉树希尔排序 ShellSort

O(n1+￡)?0<￡<1

选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1.

箱排序 BinSortO(n)

设置若干个箱子，把关键字等于?k?的记录全都装入到第?k?个箱子里?(?分配?)?，然后按序号依次将各非空的箱子首尾连接起来?(?收集?)?。

分配排序的一种：通过?"?分配?"?和?"?收集?"?过程来实现排序。

桶排序 BucketSortO(n)

桶排序的思想是把?[0?，?1)?划分为?n?个大小相同的子区间，每一子区间是一个桶。

分配排序的一种：通过?"?分配?"?和?"?收集?"?过程来实现排序。

冒泡排序

冒泡排序算法的思想：很简单，每次遍历完序列都把最大（小）的元素放在最前面，然后再对剩下的序列重复前面的一个过程，每次遍历完之后待排序序列就少一个元素，当待排序序列减小为只有一个元素的时候排序就结束了。因此，复杂度在最坏的情况下是O（N ^ 2）。

public static void QuickSort(int[] array, int low, int hight){            if(array==null || array.length==0){            return;      }            if(low<hight){            int n = Partition(array, low, hight);            QuickSort(array, 0, n);            QuickSort(array, n+1, hight);      }      }// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素private static int Partition(int[] array, int low, int hight){            // 采用子序列的第一个元素为枢纽元素      int pivot = array[low];            int temp = 0;      while(low<hight){                        // 从后往前在后半部分中寻找第一个小于枢纽元素的元素            while(low<hight && array[hight]>=pivot){                  hight--;            }            // 将这个比枢纽元素小的元素交换到前半部分            temp = array[low];            array[low] = array[hight];            array[hight] = pivot;                        // 从前往后在前半部分中寻找第一个大于枢纽元素的元素            while(low<hight && array[low]<=pivot){                  low++;            }            // 将这个比枢纽元素大的元素交换到后半部分            temp = array[low];            array[low] = array[hight];            array[hight] = temp;                  }      // 返回枢纽元素所在的位置      return low;}