java 八大排序算法
常用的排序算法主要包括：
- 插入排序
直接插入排序
希尔排序 - 交换排序
冒泡排序
快速排序 - 选择排序
简单选择排序
堆排序 - 归并排序
- 基数排序
交换排序
冒泡排序
冒泡排序是最简单的一种排序算法。
- 思想
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
一句话概括：每遍历一次，就把最大的元素放在最后。 - 算法实现
package sort;
/**
* 冒泡排序
* 思路：
* 依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
* 第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；
* 第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；
* 依次类推，每一趟比较次数-1；
* ……
*/
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] arr){
int temp=0;
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+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[]= {65,58,95,10,57,62,13,106,78,23,85};
System.out.println("排序前："+Arrays.toString(arr));
System.out.println("-------------------------------------------------------");
bubbleSort(arr);
System.out.println("-------------------------------------------------------");
System.out.println("排序后："+Arrays.toString(arr));
}
}
- 排序结果
排序前：[65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85]
-------------------------------------------------------
第[1]轮，排序结果:[58, 65, 10, 57, 62, 13, 95, 78, 23, 85, 106]
第[2]轮，排序结果:[58, 10, 57, 62, 13, 65, 78, 23, 85, 95, 106]
第[3]轮，排序结果:[10, 57, 58, 13, 62, 65, 23, 78, 85, 95, 106]
第[4]轮，排序结果:[10, 57, 13, 58, 62, 23, 65, 78, 85, 95, 106]
第[5]轮，排序结果:[10, 13, 57, 58, 23, 62, 65, 78, 85, 95, 106]
第[6]轮，排序结果:[10, 13, 57, 23, 58, 62, 65, 78, 85, 95, 106]
第[7]轮，排序结果:[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
第[8]轮，排序结果:[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
第[9]轮，排序结果:[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
第[10]轮，排序结果:[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
-------------------------------------------------------
排序后：[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
- 优化思路
加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。 - 优化代码
package sort;
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] arr){
int temp=0;
int flag=0;
for(int i=0;i<arr.length-1;i++) {
flag=0;//是否进行了交换的标识符
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;
flag=1;
}
}
if(flag==0) {
break;
}
System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
}
}
public static void main(String[] args) {
//int arr[]= {65,58,95,10,57,62,13,106,78,23,85};
int arr[]= {11,22,33,44,55,66};
System.out.println("排序前："+Arrays.toString(arr));
System.out.println("-------------------------------------------------------");
bubbleSort(arr);
System.out.println("-------------------------------------------------------");
System.out.println("排序后："+Arrays.toString(arr));
}
}
- 排序结果
排序前：[11, 22, 33, 44, 55, 66]
-------------------------------------------------------
-------------------------------------------------------
排序后：[11, 22, 33, 44, 55, 66]
快速排序
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
-
思想
快速排序使用分治策略来把一个序列分为两个子序列。步骤为：从数列中挑出一个元素，称为"基准"。
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是0或1，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。 -
算法实现
package sort;
import java.util.Arrays;
/**
* 快速排序
* 思路：
* 选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
* 一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。
* 找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。
* 直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
* 接着分别比较左右两边的序列，重复上述的循环。
*
* @author 54060
*
*/
public class QuickSort {
public static void quickSort(int [] arr,int left,int right) {
int pivot=0;
if(left<right) {
pivot=partition(arr,left,right);
quickSort(arr,left,pivot-1);
quickSort(arr,pivot+1,right);
}
}
private static int partition(int[] arr,int left,int right) {
int key=arr[left];
while(left<right) {
while(left<right && arr[right]>=key) {
right--;
}
arr[left]=arr[right];
while(left<right && arr[left]<=key) {
left++;
}
arr[right]=arr[left];
}
arr[left]=key;
return left;
}
public static void main(String[] args) {
int arr[]= {65,58,95,10,57,62,13,106,78,23,85};
System.out.println("排序前："+Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("排序后："+Arrays.toString(arr));
}
}
- 排序结果
排序前：[65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85]
排序后：[10, 13, 23, 57, 58, 62, 65, 78, 85, 95, 106]
选择排序
直接选择排序
- 思路
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 - 算法实现
package sort;
import java.util.Arrays;
/**
* 选择排序
* 1.找到数组中最小的那个元素
* 2.将最小的这个元素和数组中第一个元素交换位置
* 3.在剩下的元素中找到最小的的元素，与数组第二个元素交换位置
* 重复以上步骤，即可以得到有序数组。
* @author 54060
*
*/
public class SelectionSort {
//{ 5,3,6,2,10 }->{2,3,6,5,10}->{2,3,6,5,10}->{2,3,5,6,10}->{2,3,5,6,10}
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int k = i;
// 找出最小值的小标
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[k]) {
k = j;
}
}
// 将最小值放到排序序列开头（调换位置）
if (k > i) {//如果第i个就是最小的，则不用交换了
int tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
}
}
public static void main(String[] args) {
int[] arr = {5,3,6,2,10};
System.out.println("排序前："+Arrays.toString(arr));
selectionSort(arr);
System.out.println("排序后："+Arrays.toString(arr));
}
}
- 排序结果
排序前：[5, 3, 6, 2, 10]
排序后：[2, 3, 5, 6, 10]
堆排序
- 堆的定义
n个元素的序列{k1，k2，…,kn}当且仅当满足下列关系之一时，称之为堆。
情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小顶堆）
情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大顶堆）
其中i=1,2,…,n/2向下取整;
若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。
由此，若序列{k1，k2，…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。 - 堆排序
初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。 - 堆排序的实现
因此，实现堆排序需解决两个问题：
- 如何将n 个待排序的数建成堆；
- 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。
首先讨论第2个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法：
1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
2）将根结点与左、右子树中较小元素的进行交换。
3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.
4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.
5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。如图：
再讨论对第2个问题：n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。
2）筛选从第个结点为根的子树开始，该子树成为堆。
3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）
-
对于堆节点的访问：
父节点i的左子节点在位置：(2i+1);
父节点i的右子节点在位置：(2i+2);
子节点i的父节点在位置：floor((i-1)/2); -
算法实现
package sort;
import java.util.Arrays;
/**
* 堆排序
* @author 54060
*
*/
public class HeapSort {
/*
* 创建小顶堆：双亲节点小于子节点的值。从叶子节点开始，直到根节点。这样建立的堆定位最小值
*/
private void createLittleHeap(int[] data, int last) {
for (int i = (last- 1) / 2; i >= 0; i--) { //找到最后一个叶子节点的双亲节点
// 保存当前正在判断的节点
int parent = i;
// 若当前节点的左子节点存在，即子节点存在
while (2 * parent + 1 <= last) {
// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
int bigger = 2 * parent + 1;//bigger指向左子节点
if (bigger < last) { //说明存在右子节点
if (data[bigger] > data[bigger+ 1]) { //右子节点>左子节点时
bigger=bigger+1; //bigger取左子节点和右子节点最小的那个。因为父节点要小于这两个节点的值
}
}
//下-->上-->下
if (data[parent] > data[bigger]) { //若双亲节点值大于子节点中最小的
// 若当前节点值比子节点最小值大，则交换2者的值，交换后将biggerIndex值赋值给k
swap(data, parent, bigger);
parent = bigger;
} else {
break;
}
}
}
}
public void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
//只用两个数完成交换
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
public static void main(String[] args) {
int arr[] = {3,1,5,7,2,4,9,6,10,8};
System.out.println("排序前："+Arrays.toString(arr));
HeapSort heapSort = new HeapSort();
for(int i=0;i<arr.length;i++){
heapSort.createLittleHeap(arr,arr.length-1-i);//创建堆,创建的是小顶堆。每次循环完，二叉树的根节点都是最小值，所以与此时的未排好部分最后一个值交换位置
heapSort.swap(arr, 0, arr.length - 1 - i);//与最后一个值交换位置，最小值找到了位置
System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
}
System.out.println("排序后："+Arrays.toString(arr));
}
}
插入排序
直接插入排序
- 思路
遍历数组，遍历到i时，a0,a1…ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。可见相等元素比较时，原来靠后的还是排在后边，所以插入排序是稳定的。 - 算法实现
package sort;
import java.util.Arrays;
/**
* 插入排序
* 插入排序类似整理扑克牌，将每一张牌插到其他已经有序的牌中适当的位置。
* 插入排序由N-1趟排序组成，对于P=1到N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。
* 简单的说，就是插入排序总共需要排序N-1趟，从index为1开始，讲该位置上的元素与之前的元素比较，放入合适的位置，这样循环下来之后，即为有序数组。
* @author 54060
*
*/
public class InsertSort {
public static void InsertSort(int[] arr) {
int i, j;
int insertNode;// 要插入的数据
// 从数组的第二个元素开始循环将数组中的元素插入
for (i = 1; i < arr.length; i++) {
// 设置数组中的第2个元素为第一次循环要插入的数据
insertNode = arr[i];
j = i - 1;
// 如果要插入的元素小于第j个元素，就将第j个元素向后移
while ((j >= 0) && insertNode < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
arr[j + 1] = insertNode;
System.out.println("第["+i+"]轮，排序结果:"+Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[] = { 53, 27, 36, 15, 69, 42 };
System.out.println("排序前："+Arrays.toString(arr));
InsertSort(arr);
System.out.println("排序后："+Arrays.toString(arr));
}
}
- 排序结果
排序前：[53, 27, 36, 15, 69, 42]
第[1]轮，排序结果:[27, 53, 36, 15, 69, 42]
第[2]轮，排序结果:[27, 36, 53, 15, 69, 42]
第[3]轮，排序结果:[15, 27, 36, 53, 69, 42]
第[4]轮，排序结果:[15, 27, 36, 53, 69, 42]
第[5]轮，排序结果:[15, 27, 36, 42, 53, 69]
排序后：[15, 27, 36, 42, 53, 69]
希尔排序
在前面文章中介绍的直接插入排序，它对于已经基本有序的数据进行排序，效率会很高，而如果对于最初的数据是倒序排列的，则每次比较都需要移动数据，导致算法效率降低。
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是不稳定排序算法。
- 思路
将待排序数组按照步长进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将步长折半减小，循环上述操作；当步长=1时，利用直接插入，完成排序。
可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。 - 算法实现
package sort;
import java.util.Arrays;
/**
* 希尔排序
* @author 54060
*/
public class ShellSort {
public static void sort(int arr[]) {
int d=arr.length/2;
int x,j,k=1;
while(d>=1) {
for(int i=d;i<arr.length;i++) {
x=arr[i];
j=i-d;
//直接插入排序，会向前找所适合的位置
while(j>=0 && arr[j]>x) {
//交换位置
arr[j+d]=arr[j];
j=j-d;
}
arr[j+d]=x;
}
d=d/2;
System.out.println("第["+(k++)+"]轮，排序结果:"+Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[]={32,24,95,45,75,22,95,49,3,76,56,11,37,58,44,19,81};
System.out.println("排序前："+Arrays.toString(arr));
sort(arr);
System.out.println("排序后："+Arrays.toString(arr));
}
}
- 排序结果
排序前：[32, 24, 95, 45, 75, 22, 95, 49, 3, 76, 56, 11, 37, 58, 44, 19, 81]
第[1]轮，排序结果:[3, 24, 56, 11, 37, 22, 44, 19, 32, 76, 95, 45, 75, 58, 95, 49, 81]
第[2]轮，排序结果:[3, 22, 44, 11, 32, 24, 56, 19, 37, 58, 95, 45, 75, 76, 95, 49, 81]
第[3]轮，排序结果:[3, 11, 32, 19, 37, 22, 44, 24, 56, 45, 75, 49, 81, 58, 95, 76, 95]
第[4]轮，排序结果:[3, 11, 19, 22, 24, 32, 37, 44, 45, 49, 56, 58, 75, 76, 81, 95, 95]
排序后：[3, 11, 19, 22, 24, 32, 37, 44, 45, 49, 56, 58, 75, 76, 81, 95, 95]
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
- 思路
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 - 算法实现
package sort;
/**
* 归并排序
* 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
* 归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
* @author 54060
*
*/
import java.util.Arrays;
public class MergeSort {
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = left + (right-left) / 2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
System.out.println("排序前："+Arrays.toString(arr));
sort(arr);
System.out.println("排序后："+Arrays.toString(arr));
}
}
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
- 思路
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 - 实现方案
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。 - 算法实现
package sort;
import java.util.Arrays;
/**
* 基数排序
*
* LSD具体算法描述如下：
* 取得数组中的最大数，并取得位数；
* arr为原始数组，从最低位开始取每个位组成radix数组；
* 对radix进行计数排序（利用计数排序适用于小范围数的特点）。
* @author 54060
*
*/
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr.length <= 1) return;
//取得数组中的最大数，并取得位数
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int maxDigit = 1;
while (max / 10 > 0) {
maxDigit++;
max = max / 10;
}
//申请一个桶空间
int[][] buckets = new int[10][arr.length];
int base = 10;
//从低位到高位，对每一位遍历，将所有元素分配到桶中
for (int i = 0; i < maxDigit; i++) {
int[] bktLen = new int[10]; //存储各个桶中存储元素的数量
//分配：将所有元素分配到桶中
for (int j = 0; j < arr.length; j++) {
int whichBucket = (arr[j] % base) / (base / 10);
buckets[whichBucket][bktLen[whichBucket]] = arr[j];
bktLen[whichBucket]++;
}
//收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
int k = 0;
for (int b = 0; b < buckets.length; b++) {
for (int p = 0; p < bktLen[b]; p++) {
arr[k++] = buckets[b][p];
}
}
base *= 10;
}
}
public static void main(String[] args) {
int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50};
System.out.println("排序前: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
八大排序算法总结
-
时间复杂度
(1)平方阶(O(n2))排序
各类简单排序：直接插入、直接选择和冒泡排序；
(2)线性对数阶(O(nlog2n))排序
快速排序、堆排序和归并排序；
(3)O(n1+§))排序,§是介于0和1之间的常数。
希尔排序。
(4)线性阶(O(n))排序
基数排序，此外还有桶、箱排序。 -
论是否有序的影响
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 -
稳定性
排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较； -
稳定的排序算法：
冒泡排序、插入排序、归并排序和基数排序 -
不稳定的排序算法：
选择排序、快速排序、希尔排序、堆排序