排序的常用算法有哪些啊，哪个效率最高啊？谁来回答一下

常用的排序算法有选择排序，冒泡排序和快速排序，

java工具类中的Arrays.sort();其实就是快速排序，其底部是三层for循环，效率最高的当然是快速排序。

class ArrayDemo
{
        public static void main(String[] args)
        {
                //可以通过“arrayName.length”来获取数组长度
                int[] arr = {1,4,9,2,5,6,3,4,7,5};
                printArray(arr);
                //bubbleSort(arr);
                //selectSort(arr);
                quickSort(arr,0,arr.length-1);
                printArray(arr);
        }
        //数组的遍历
        public static void printArray(int[] arr)
        {
                System.out.print("[");
                for(int x=0;x<arr.length;x++)
                {
                        if(x<arr.length-1)
                                System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]+"]");
                }
        }
        //将数组中的两个元素位置互换。
        public static void swap(int[] arr,int a,int b)
        {
                int temp = arr[a];
                arr[a] = arr[b];
                arr[b] = temp;
        }
        //冒泡排序算法。
        public static void bubbleSort(int[] arr)
        {
                for(int x=0;x<arr.length-1;x++)
                        for(int y=0;y<arr.length-x-1;y++)
                        {
                                if(arr[y]>arr[y+1])
                                        swap(arr,y,y+1);
                        }
        }
        //选择排序算法。
        public static void selectSort(int[] arr)
        {
                for(int x=0;x<arr.length-1;x++)
                        for(int y=x+1;y<arr.length;y++)
                        {
                                if(arr[x]>arr[y])
                                {
                                                swap(arr,x,y);
                                }
                        }
        }
        //快速排序。
        public static void quickSort(int[] arr,int start,int end)
        {        
                int i=start,j=end;
                //当arr指向为空或者数组的长队为零，直接返回
                if((arr==null)||(arr.length==0))
                        return;
                while(i<j)
                {
                        //以i脚标的数值为关键字，从右侧开始向左侧比较
                        while(i<j&&arr[i]<=arr[j])
                        {
                                j--;
                        }
                        //从右侧开始向左侧比较，找到第一个比i脚标的数值小的，交换位置。
                        if(i<j)
                        {
                                swap(arr,i,j);
                        }
                        //以j脚标的数值为关键字，从左侧开始向右侧比较
                        while(i<j&&arr[i]<arr[j])
                        {
                                i++;
                               
                        }
                        //从左侧开始向油侧比较，找到第一个不小于j脚标的数值，交换位置。
                        if(i<j)
                        {
                                swap(arr,i,j);
                        }
                }
                //递归调用。直到完成排序
                if(i-start>1)
                {
                        quickSort(arr,start,i-1);
                }
                if(end-i>1)
                {
                        quickSort(arr,i+1,end);
                }
        }
}

冒泡排序和选择排序时比较易懂的，毕老师视频也有详细讲解，这里就忽略了，主要分享下插入排序和快速排序：

1、插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x
实现：
public static void insertSort(int a[]) {
int len = a.length;
for (int i = 1; i < len; i++) {
int temp = a[i];// 待插入的值
int index = i;// 待插入的位置
while (index > 0 && a[index - 1] > temp) {
a[index] = a[index - 1];// 待插入的位置重新赋更大的值
index--;// 位置往前移
}
a[index] = temp;
}
}

2、快速排序（也叫归并排序），这个我也是费了好大劲才终于理解，下面是我在一个网站学习到的，不是我自己写的，供分享：
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] （虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ，我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分）那么需要的额外数组的长度为 4 + 4 = 8 。
实现：
public static int partition(int a[], int low, int height) {
int key = a[low];
while (low < height) {
while (low < height && a[height] >= key)
height--;
a[low] = a[height];

while (low < height && a[low] <= key)
low++;
a[height] = a[low];
}
a[low] = key;
return low;
}

public static void quickSort(int a[], int low, int height) {
if (low < height) {
int result = partition(a, low, height);
quickSort(a, low, result - 1);
quickSort(a, result + 1, height);
}
}

效率排行：快速排序>插入排序>选择排序>冒泡排序

1、直接插入排序：直接插入排序(straight insertion sort)的做法是：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。

1. public static int[] insertSort(int[] arr)
   
2. {  
   
3.         for(int i=1; i<arr.length;i++)
   
4.         {  
   
5.                 for(int j=i;j>0;j--)
   
6.                 {  
   
7.                         if(arr[j]<arr[j-1])
   
8.                         {  
   
9.                                 int temp=arr[j-1];
   
10.                                 arr[j-1]=arr[j];
    
11.                                 arr[j] =temp;
    
12.                         }
    
13.                         else  
    
14.                                 break;
    
15.                 }
    
16.         }  
    
17.         return arr;
    
18. }  
    

复制代码

2、折半插入排序折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。

1. public static int[] halfInsert(int[] arr)
   
2. {  
   
3.         for (int i=1;i<arr.length;i++) //从第二个元素开始，需要做n-1趟插入排序，第一个元素自成有序区
   
4.         {
   
5.                 int temp=arr[i];// 暂存  
   
6. 
   
7.                 //low和high分别指向有序区中的第一个和最后一个元素  
   
8.                 int low=0;// 定义从第一个元素开始为有序区  
   
9.         int high=i-1;// 有序区的元素从一个开始逐渐增加
   
10.         
    
11.                 //寻找在有序区中插入的位置，最后使high<low，就找到插入的位置,为high+1；也是low的位置
    
12.                 while(low<=high)  
    
13.                 {
    
14.                         int m=(low + high)/2;// 有序区的中间元素  
    
15.                         if(temp<arr[m])//如果比中间的元素小，则插入位置在低半区  
    
16.                                 high=m-1;  
    
17.                                 else //否则，插入位置在高半区
    
18.                                         low=m+1;  
    
19.                 }  
    
20. 
    
21.                 // 把从low开始以后或high+1以后的元素向后移动，插入
    
22.                 for(int j=i;j>low;j--)  
    
23.                         arr[j]=arr[j-1];// 移动元素
    
24.                 arr[low]=temp;// 插入在合适的位置  
    
25.         }  
    
26.         return arr;  
    
27. }   
    

复制代码

3、快速排序:通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A，将A赋给A[j]；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

1. public static void quickSort(int[] arr, int low, int high)
   
2. {   
   
3.         p=get(arr,low,high);   
   
4.         quickSort(arr,low,p-1);   
   
5.         quickSort(arr,p+1,high);   
   
6. }   
   
7. public static int get(int[] arr,int low,int high)
   
8. {   
   
9.      compare=arr[low];   
   
10.      while(low<high)//无论如何置换, 被置换的都包含compare的值
    
11.         {   
    
12.          while(low<high && arr[high]>=compare)      
    
13.               high--;   
    
14.          temp = arr[low];  //在 low<high 的情况下找到a[high]<compare并置换  
    
15.          arr[low] = arr[high];  
    
16.          arr[high] = temp;  
    
17.   
    
18.          while(low<high && arr[low]<=compare)   
    
19.               low++;   
    
20.           temp = arr[low];//在 low<high 的情况下找到a[low]>compare并置换      
    
21.           arr[low] = arr[high];   
    
22.           arr[high] = temp;   
    
23.      }   
    
24.      return low; //while(low==hight)停止循环, 并返回枢轴位置   
    
25. }  

复制代码

4、希尔排序(缩小增量法) 属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
h = 3 * h +1
反过来程序需要反向计算h序列，应该使用
h=(h-1)/3

1. public static void shellSort(int[] arr) // 计算出最大的h值
   
2. {
   
3.         int h=1;
   
4.         while(h<=arr.length/3)
   
5.                 h=h*3+1;
   
6.         while(h>0)
   
7.         {
   
8.                 for(int i=h;i<arr.length;i+=h)
   
9.                 {
   
10.                         if(arr[i]<arr[i-h])
    
11.                         {
    
12.                                 int tmp=arr[i];
    
13.                                 int j=i-h;
    
14.                                 while(j>=0&&arr[j]>tmp)
    
15.                                 {
    
16.                                         arr[j+h]=arr[j];
    
17.                                         j-=h;
    
18.                                 }
    
19.                                 arr[j+h]=tmp;
    
20.                         }                 
    
21.                 }
    
22.                 h=(h-1)/3; // 计算出下一个h值
    
23.         }
    
24. }

复制代码

5、堆排序：堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O(1)， 最坏时间复杂度为O(nlog2n) ，堆排序的堆序的平均性能较接近于最坏性能。 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。

大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

1. public static void heapSort(int[] arr)
   
2. {
   
3.         for(int i=0;i<arr.length;i++)
   
4.         {
   
5.                 createMaxdHeap(arr,arr.length-i-1);
   
6.                 swap(arr, 0, arr.length-i-1);
   
7.                 for(int i = 0; i < arr.length; i++)
   
8.                         System.out.print(arr[i] + "\t");
   
9.         }
   
10. }
    
11. 
    
12. public static void createMaxdHeap(int[] arr, int lastIndex)
    
13. {
    
14.         for(int i=(lastIndex-1)/2;i>=0;i--)
    
15.         {
    
16.                 int k=i;// 保存当前正在判断的节点  
    
17.                 while (2*k+1<=lastIndex) // 若当前节点的子节点存在
    
18.                 {
    
19.                         int biggerIndex=2*k+1; // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
    
20.                         if(biggerIndex<lastIndex)// 若右子节点存在，否则此时biggerIndex应该等于 lastIndex
    
21.                                 if(arr[biggerIndex]<arr[biggerIndex+1])// 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值
    
22.                                         biggerIndex++;
    
23.                         if(arr[k] < arr[biggerIndex]) // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k
    
24.                         {
    
25.                                 swap(arr, k, biggerIndex);
    
26.                                 k = biggerIndex;
    
27.                         }
    
28.                         else
    
29.                                 break;
    
30.                 }
    
31.         }
    
32. }
    
33. 
    
34. public static void swap(int[] arr, int i, int j)
    
35. {
    
36.         if(i==j)
    
37.                 return;
    
38.         arr[i] = arr[i] + arr[j];
    
39.         arr[j] = arr[i] - arr[j];
    
40.         arr[i] = arr[i] - arr[j];
    
41. }
    

复制代码

6、归并排序
归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。
工作原理：
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾

1. public static void mergeSort(int[] arr)
   
2. {
   
3.         sort(arr, 0, arr.length - 1);
   
4. }
   
5. 
   
6. public static void sort(int[] arr, int left, int right)
   
7. {
   
8.         if(left>=right)
   
9.                 return;
   
10.         int center=(left+right)/2; // 找出中间索引
    
11.         sort(arr,left,center);// 对左边数组进行递归
    
12.         sort(arr,center+1,right); // 对右边数组进行递归
    
13.         merge(arr,left,center,right);// 合并  
    
14.         for(int i=0;i<arr.length;i++)
    
15.                 System.out.print(arr[i] + "\t");
    
16. }
    
17. 
    
18. /*
    
19. 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
    
20. arr:数组对象
    
21. left:左数组的第一个元素的索引
    
22. center:左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
    
23. right:右数组最后一个元素的索引
    
24. */
    
25. public static void merge(int[] arr, int left, int center, int right)
    
26. {
    
27.         int[] tmpArr = new int[arr.length];// 临时数组  
    
28.         int mid = center + 1;// 右数组第一个元素索引  
    
29.         int third = left; // third 记录临时数组的索引
    
30.         int tmp = left;// 缓存左数组第一个元素的索引  
    
31.         while(left<=center&&mid<=right)
    
32.         {
    
33.                 if(arr[left]<=arr[mid]) // 从两个数组中取出最小的放入临时数组  
    
34.                         tmpArr[third++]=arr[left++];
    
35.                 else
    
36.                         tmpArr[third++]=arr[mid++];
    
37.         }
    
38.         while(mid<=right) // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
    
39.                 tmpArr[third++]=arr[mid++];
    
40.                 while(left<=center)
    
41.                         tmpArr[third++] = arr[left++];
    
42.                 while(tmp<=right)// 将临时数组中的内容拷贝回原数组中 （原left-right范围的内容被复制回原数组）
    
43.             arr[tmp]=tmpArr[tmp++];
    
44. }
    

复制代码

7、基数排序
基数排序已经不再是一种常规的排序方式，它更多地像一种排序方法的应用，基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键字，第3个排序关键字......然后，根据子关键字对待排序数据进行排序。
多关键字排序时有两种解决方案：
最高位优先法（MSD）(Most Significant Digit first)
最低位优先法（LSD）(Least Significant Digit first)
例如，对如下数据序列进行排序。
192,221,12,23
可以观察到它的每个数据至多只有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。人得习惯思维是最高位优先方式。
对于多关键字排序来说，程序将待排数据拆分成多个子关键字后，对子关键字排序既可以使用桶式排序，也可以使用任何一种稳定的排序方法。

1. public static void radixSort(int[] arr,int radix,int d)
   
2. {
   
3.         int[] tmp=new int[arr.length];// 缓存数组
   
4.         int[] buckets=new int[radix];// buckets用于记录待排序元素的信息,buckets数组定义了max-min个桶  
   
5.         for(int i=0,rate=1;i<d;i++)
   
6.         {
   
7.                 Arrays.fill(buckets,0); // 重置count数组，开始统计下一个关键字
   
8.                 System.arraycopy(arr, 0,tmp,0,arr.length); // 将data中的元素完全复制到tmp数组中
   
9.                
   
10.                 for(int j=0;j<arr.length;j++)  // 计算每个待排序数据的子关键字
    
11.                 {
    
12.                         int subKey=(tmp[j]/rate)%radix;
    
13.                         buckets[subKey]++;
    
14.                 }
    
15.                 for(int j=1;j<radix;j++)
    
16.                         buckets[j]=buckets[j]+buckets[j-1];
    
17.                 for(int m=arr.length-1;m>=0;m--)// 按子关键字对指定的数据进行排序
    
18.                 {
    
19.                         int subKey=(tmp[m]/rate)%radix;
    
20.                         arr[--buckets[subKey]]=tmp[m];
    
21.                 }
    
22.                 rate *= radix;
    
23.         }
    
24. }

复制代码

niubiquanshidashen

一、冒泡（Bubble）排序——相邻交换
二、选择排序——每次最小/大排在相应的位置
三、插入排序——将下一个插入已排好的序列中
四、壳（Shell）排序——缩小增量
五、归并排序
六、快速排序
七、堆排序
八、拓扑排序
九、锦标赛排序
十、基数排序
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。