几种常见排序算法的兑现[内部排序]
几种常见排序算法的实现[内部排序]
马上要找开始找工作了
抽点空对各种排序算法进行一下总结，随手从*上搜索了一下。
排序算法大概分这么多种
稳定的
冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外空间
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
合并排序 （merge sort）— O(n log n); 需要 O(n) 额外空间
原地合并排序 — O(n2)
二叉排序树排序 （Binary tree sort） — O(n log n)期望时间; O(n2)最坏时间; 需要 O(n) 额外空间
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间
基数排序 （radix sort）— O(n·k); 需要 O(n) 额外空间
Gnome 排序 — O(n2)
图书馆排序 — O(n log n) with high probability, 需要 (1+ε)n 额外空间
[编辑] 不稳定
选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
组合排序 — O(n log n)
堆排序 （heapsort）— O(n log n)
平滑排序 — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数列表一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最坏情况时间，需要 额外的 O(n + k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）
[编辑] 不实用的排序算法
Bogo排序 — O(n × n!) 期望时间，无穷的最坏情况。
Stupid sort — O(n3); 递归版本需要 O(n2) 额外存储器
珠排序（Bead sort） — O(n) or O(√n), 但需要特别的硬件
Pancake sorting — O(n), 但需要特别的硬件
这里面有很多我听说过的，很多没听说过的，有些用过的，有些没用过，大部分用java实现了一遍，从中看一下他们的核心思想。
一：冒泡排序
大学课程里面第一个排序算法，它的基本思想是每一个不断的遍历数组，每次遍历总是把最大的那个数找出来放到数组的尾部。经过n轮遍历之后，就排序完成。
/**
* 实现冒泡泡排序
* @return void
* @param int[]
* 它的原理是每一次都把最大的数放到最后面
* */
@SuppressWarnings("unused")
private void bubbleSort(int[] array){
//用于临时存数
int temp = 0;
for(int i = 1;i<array.length;i++){
for(int j=0;j<array.length-i;j++){
if(array[j]>array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
二：插入排序
核心思想是：将一个数插入到一个有序表中，形成一个新的有序表
/**
* 实现插入排序
* 实现原理是将后面一个数都插入到前面已经排序好的序列中
* */
@SuppressWarnings("unused")
private void insertSort(int[] array){
//从头开始遍历
for(int i = 0;i<array.length;i++){
int temp = array[i];
int j = i;
//确定每一个数的位置
while(j>=0&&array[j]>temp){
//如果有大的那么将前面的数向后面移动
array[j+1] = array[j];
j--;
}
array[j] = temp;
}
}
三：选择排序
核心思想是：遍历数组找出最大的那个数，然后插入到合适的正确的位置，这个跟冒泡很像
@SuppressWarnings("unused")
public void chooseSort(int[] array){
for(int i=0;i<array.length;i++){
//先给他一个小点的值
int max = min;
//存储那个最大数的位置
int place = -1;
for(int j=0;j<array.length-i;j++){
//找到每一轮的最大的那个数和那个数的位置
if(array[j]>max){
max = array[j];
place = j;
}
}
//然后把它们插入到合适的位置
array[place] = array[array.length-i-1];
array[array.length-i] = max;
}
}
四：堆排序
这是所有排序中我觉得最复杂的一个，核心思想：其实也是找出最大值，然后也是插入到正确位置，只是找出最大值得办法是使用大顶堆，它的根就是最大值，然后与堆的最后一个节点交换，再进行向下堆调，成为一个新堆，这样重复，直到堆为空。
那么步骤是：1：建堆2：交换3：向下堆调
/**
* 实现堆排序
* 原理：先建立一个大顶堆，将最后一个元素与第一个元素调换然后向下堆调,依次下去就能得到一个有序数组了
* 堆：大顶堆
* */
//建堆
//向下堆调
@SuppressWarnings("unused")
private void shiftDown(int[] array,int st,int end){
int parent = st;
//这里之所以加1是因为数组的下标从0开始
int lchild = 2*st+1;
int rchild = 2*st+2;
int max = 0,temp = 0;
while(lchild<end){
max = lchild;
if(rchild<end){
if(array[lchild]<array[rchild]){
max=rchild;
}
}
if(array[parent]<array[max]){
//交换数据
temp = array[parent];
array[parent] = array[max];
array[max] = temp;
//进行下一次堆调当然也可以使用递归
parent = max;
lchild = 2*parent+1;
rchild = 2*parent+2;
}
else{break;}
}
}
//创建堆
private void createHeap(int[] array){
for(int i=array.length/2-1;i>=0;i--){
shiftDown(array,i,array.length);
}
print(array);
}
//这里是堆排序的实现
public void heapSort(int[] array){
createHeap(array);
int temp = 0;
for(int i=1;i<array.length;i++){
temp = array[0];
array[0] = array[array.length-i];
array[array.length-i] = temp;
shiftDown(array,0, array.length-i-1);
}
}
五：计数排序
核心思想：对于特定元素x来说，如果确定了序列中比其小的元素的个数。那么就能确定x的位置了，a数组中的数都为非负整数。如果有负数，则因该加上一个数，使其为正。
在这个程序中我们创建了两个大数组，一个用于计数，一个用于临时存储。
/**
* 计数排序
* 对于特定的元素来说，如果确定了序列中比其小的元素的个数，那么就能确定这个元素的位置了
* */
public void countingSort(int[] array){
//int数组赋值为0
int[] count = new int[10000];
int[] copy = new int[10000];
//给count数组赋值
for(int i=0;i<array.length;i++){
count[array[i]]=1;
}
//得到比count[i]小的数只是用了一种特殊的方式
//在纸上画一下就知道了
for(int i=1;i<10000;i++){
count[i] = count[i]+count[i-1];
}
//在合适的地方放上合适的数
for(int i=array.length-1;i>=0;i--){
copy[count[array[i]]-1] = array[i];
}
//再把排序好的数据放好
for(int i=0;i<array.length;i++){
array[i] = copy[i];
}
}
六：归并排序
归并排序使用了分治的思想，将一个大的排序分为若干个小的排序
归并排序分为自顶向下，自底向上的排序，当然我们熟知的是自顶向下
后者与前者的区别主要在于后者是合并的过程，而前者是划分的过程，前者与快速排序的思想很相像。下面来看一下它的实现过程。
/**
* 合并数组的两段
* @param array int[]
* @param start
* @param end
* @param mid
* 将两个排序好的数组合并成一个
* */
public void merge(int[] array,int start,int mid,int end){
//一个辅助数组
int[] comment = new int[10000];
int s = start,m = mid,index=start;
while(s<mid&&m<end){
if(array[s]<=array[m]){
comment[index] = array[s];
s++;
}
else {
comment[index] = array[m];
m++;
}
index++;
}
//如果前面这个数组被索引完毕
if(s == mid){
while(m<end){
comment[index++] = array[m++];
}
}else{
//System.out.println("s=="+s);
while(s<end){
comment[index++] = array[s++];
}
}
for(int i = start;i<end;i++){
array[i] = comment[i];
}
}
//实现mergeSort归并排序
public void mergeSort(int[] array){
int t = 1;
int start = 0;
int i = 0;
while(t<=array.length){
start = t;
t = 2*start;
i = 0;
while((i+t)<=array.length){
merge(array, i, i+start, i+t);
i = i+t;
}
print(array);
if(i+start<array.length){
merge(array, i, i+start, array.length);
}
}
}
//这里实现的是自顶向上的排序
public void mergeSort1(int[] array, int p1, int p3) {
if((p3-p1) <= 1) return; //判断是否不需要继续递归
int p2 = (p3 + p1)/2; //计算中间位置p2
mergeSort1(array,p1,p2); //将p1 ~ p2之间递归排序
mergeSort1(array,p2,p3); //将p2 ~ p3之间递归排序
merge(array,p1,p2,p3); //合并p1~p2,p2~p3
}
七：快速排序
快速排序是一个也是典型的分治
/**
* 这里是最经典也用的最多的快速排序
* 与merge的不同在于它是一个划分的过程
* */
private int split(int[] array,int left,int right){
int key = array[left];
int temp = 0;
int low = left+1;
int high = right;
while(low<high){
if(array[low]<=key) low++;
else if(array[high]>=key) high--;
else {
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
array[left] = array[--low];
array[low] =key;
return low;
}
//实现快速排序
public void quickSort(int[] array,int low,int right){
int devide = 0;
if(low<right){
devide = split(array, low, right);
System.out.println(devide);
print(array);
quickSort(array, low, devide-1);
quickSort(array, devide+1, right);
}
}
八：希尔排序
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
/**
* 希尔排序
* h = h*3+1.初始 h=1
* */
public void shellSort(int[] array){
int h = 1;
while(h<array.length)
h = h*3+1;
h = (h-1)/3;
while(h>=1)
{
for(int i=h;i<array.length;i++)
{
int j = i-h;
int key = array[i];
while(j>=0&&array[j]>key)
{
array[j+h] = array[j];
j-=h;
}
j+=h;
array[j]=key;
}
h=(h-1)/3;
}
}
九：基数排序
这个描述起来比较复杂，算是归纳法的一种吧。实现方式就是一下的，没有这么写注释，就是按照十进制位来排序，比如先第一位排序，然后按照第二位，直到最高位，需要比较大的空间开销。
public void radixSort(int[] number, int d) {
int k=0;
int n=1;
int m=1;
int[][] temp = new int[number.length][number.length];
int[] order = new int[number.length];
while(m <= d) {
for(int i = 0; i < number.length; i++) {
int lsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(int i = 0; i < d; i++) {
if(order[i] != 0)
for(int j = 0; j < order[i]; j++) {
number[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
马上要找工作了，以上的排序算法在大学多多少少都接触过，但很长时间没有用了，有的就忘记了，现在把它们整理一遍。只是对一些常见的排序算法的一个实现，没有仔细的研究各个算法的时间复杂度空间复杂度。