十大排序算法（详解+动图+代码）

排序算法

复杂度：

一. 冒泡排序(Bubble Sort)

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

过程：

1. 比较相邻的两个数据，如果第二个数小，就交换位置。
2. 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
3. 继续重复上述过程，依次将第2.3…n-1个最小数排好位置。

#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, 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[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

优化：

• 针对问题：
  数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

• 方案：
  设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
  这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

二. 选择排序(Selction Sort)

基本思想：

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
…
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

代码：

#include<stdio.h>
int main(){
    int array[6] = {45, 7, 8, 4, 6, 90};
    for (int i=0; i<6; i++) {
        int max = i;
        for (int j=i+1; j<6; j++) {
            if (array[j] > array[max]){
                max = j;
             }
        }
        int temp = array[i];
        array[i] = array[max];
        array[max] = temp;
    }
    for(int i=0; i<6; i++){
        printf("%d\n",arr[i]);
    }
    return 0;
}

三. 插入排序(Insertion Sort)

基本思想：

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

代码：

void insertion_sort(int arr[], int len){
    int i,j,temp;
    for (i=1;i<len;i++){
            temp = arr[i];
            for (j=i;j>0 && arr[j-1]>temp;j--)
                    arr[j] = arr[j-1];
            arr[j] = temp;
    }
}

四. 希尔排序(Shell Sort)

基本思想：

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。

先将整个待排记录序列分割成为若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

过程：

代码：

void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

五. 快速排序(Quick sort)

基本思想：（分治）

1. 先从数列中取出一个数作为key值；
2. 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
3. 对左右两个小数列重复第二步，直至各区间只有1个数。
   
   

迭代法：

typedef struct _Range {
    int start, end;
} Range;
Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負值時引發段錯誤（Segment Fault）
    // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
        int left = range.start, right = range.end;
        do
        {
            while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求
            while (arr[right] > mid) --right; //檢測基準點右側是否符合要求
 
            if (left <= right)
            {
                swap(&arr[left],&arr[right]);
                left++;right--;               // 移動指針以繼續
            }
        } while (left <= right);
 
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}

递归法：

void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

六. 归并排序(Merge Sort)

基本思想：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。它使用了递归分治的思想；相当于：左半边用尽，则取右半边元素；右半边用尽，则取左半边元素；右半边的当前元素小于左半边的当前元素，则取右半边元素；右半边的当前元素大于左半边的当前元素，则取左半边的元素。

过程：

迭代法：

int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

递归法：

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

七. 堆排序(Heap Sort)

基本思想：堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

过程：

图示：（88,85,83,73,72,60,57,48,42,6）

Java代码：

//构建最小堆
public static void MakeMinHeap(int a[], int n){
 for(int i=(n-1)/2 ; i>=0 ; i--){
     MinHeapFixdown(a,i,n);
 }
}
//从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
public static void MinHeapFixdown(int a[],int i,int n){

   int j = 2*i+1; //子节点
   int temp = 0;

   while(j<n){
       //在左右子节点中寻找最小的
       if(j+1<n && a[j+1]<a[j]){  
           j++;
       }

       if(a[i] <= a[j])
           break;

       //较大节点下移
       temp = a[i];
       a[i] = a[j];
       a[j] = temp;

       i = j;
       j = 2*i+1;
   }
}

public static void MinHeap_Sort(int a[],int n){
  int temp = 0;
  MakeMinHeap(a,n);

  for(int i=n-1;i>0;i--){
      temp = a[0];
      a[0] = a[i];
      a[i] = temp;
      MinHeapFixdown(a,0,i);
  }    
}

八. 计数排序

基本思想：

将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

java代码：

/**
     * 输入数组的元素都是介于0..k之间的
     * @param data 待排序数组
     * @param k 最大元素
     * @return 排序结果
     */
    public static int[] sort(int[] data, int k) {
        // 存放临时数据的数组tmp，初始元素都是0；k为数组中最大元素
        int[] tmp = new int[k + 1];

        // 计算数组中每个元素i出现的次数，存入数组tmp中的第i项，即原数组中的元素值为tmp数组中的下标
        for (int i = 0; i <= data.length - 1; i++) {
            tmp[data[i]]++;
        }
        // 计算数组中小于等于每个元素的个数,即从tmp中的第一个元素开始，每一项和前一项相加
        for (int j = 1; j <= k; j++) {
            tmp[j] = tmp[j] + tmp[j - 1];
        }
        // result数组用来来存放排序结果
        int[] result = new int[data.length];
        for (int i = data.length - 1; i >= 0; i--) {
            result[tmp[data[i]] - 1] = data[i];
            tmp[data[i]]--;
        }
        return result;
    }

package test;

public class jishu {
    public static int[] countingSort(int[] theArray) {
        int[] lastArray = new int[theArray.length];
        for(int i = 0; i < theArray.length; i++) {
            int count = 0;
            for(int j = 0; j < theArray.length; j++) {
                if(theArray[i] > theArray[j]) {
                    count++;
                }
            }
            lastArray[count] = theArray[i];
        }
        return lastArray;
    }
    public static void main(String[] args) {
        int []theArray = {6, 4, 5, 1, 8, 7, 2, 3};
        System.out.print("之前的排序：");
        for(int i = 0; i < theArray.length; i++) {
            System.out.print(theArray[i] + " ");
        }

        int []resultArray = countingSort(theArray);

        System.out.print("计数排序：");
        for(int i = 0; i < resultArray.length; i++) {
            System.out.print(resultArray[i] + " ");
        }
    }

}

九. 桶排序

基本思想：

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

Java代码：

public static void bucketSort(double array[]) {
        int length = array.length;
        ArrayList arrList[] = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            //0.7到0.79放在第8个桶里,编号7；第一个桶放0到0.09
            int temp = (int) Math.floor(10 * array[i]);
            if (null == arrList[temp])
                arrList[temp] = new ArrayList();
            arrList[temp].add(array[i]);
        }
        // 对每个桶中的数进行插入排序
        for (int i = 0; i < length; i++) {
            if (null != arrList[i]) {
                Collections.sort(arrList[i]);
            }
        }
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (null != arrList[i]) {
                Iterator iter = arrList[i].iterator();
                while (iter.hasNext()) {
                    Double d = (Double) iter.next();
                    array[count] = d;
                    count++;
                }
            }
        }
    }

package test;

public class tong {
    private int[] buckets;
      private int[] array;

      public tong(int range,int[] array){
        this.buckets = new int[range];
        this.array = array;
      }

      /*排序*/
      public void sort(){
        if(array!=null && array.length>1){
          for(int i=0;i<array.length;i++){
            buckets[array[i]]++;
          }
        }
      }

      /*排序输出*/
      public void sortOut(){
        //倒序输出数据
        for (int i=buckets.length-1; i>=0; i--){
          for(int j=0;j<buckets[i];j++){
            System.out.print(i+"\t");
          }
        }
      }


      public static void main(String[] args) {
            testBucketsSort();
          }

          private static void testBucketsSort(){
            int[] array = {5,7,3,5,4,8,6,4,1,2};
            tong bs = new tong(10, array);
            bs.sort();
            bs.sortOut();//输出打印排序
          }

}

十. 基数排序(Radix Sort)

基本思想：

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

java代码：

private static void radixSort(int[] array,int radix, int distance) {
        int length = array.length;
        int[] temp = new int[length];
        int[] count = new int[radix];
        int divide = 1;

        for (int i = 0; i < distance; i++) {

            System.arraycopy(array, 0,temp, 0, length);
            Arrays.fill(count, 0);

            for (int j = 0; j < length; j++) {
                int tempKey = (temp[j]/divide)%radix;
                count[tempKey]++;
            }

            for (int j = 1; j < radix; j++) {
                count [j] = count[j] + count[j-1];
            }
            for (int j = length - 1; j >= 0; j--) {
                int tempKey = (temp[j]/divide)%radix;
                count[tempKey]--;
                array[count[tempKey]] = temp[j];
            }
            divide = divide * radix;
        }
    }

package test;

    /**
     * 基数排序
     * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
     * d为位数,r为分配后链表的个数
     *
     *
     */
    public class ji_shu {
        //pos=1表示个位，pos=2表示十位
        public static int getNumInPos(int num, int pos) {
            int tmp = 1;
            for (int i = 0; i < pos - 1; i++) {
                tmp *= 10;
            }
            return (num / tmp) % 10;
        }
        //求得最大位数d
        public static int getMaxWeishu(int[] a) {
            int max = a[0];
            for (int i = 0; i < a.length; i++) {
                if (a[i] > max)
                        max = a[i];
            }
            int tmp = 1, d = 1;
            while (true) {
                tmp *= 10;
                if (max / tmp != 0) {
                    d++;
                } else
                        break;
            }
            return d;
        }
        public static void radixSort(int[] a, int d) {
            int[][] array = new int[10][a.length + 1];
            for (int i = 0; i < 10; i++) {
                array[i][0] = 0;
                // array[i][0]记录第i行数据的个数
            }
            for (int pos = 1; pos <= d; pos++) {
                for (int i = 0; i < a.length; i++) {
                    // 分配过程
                    int row = getNumInPos(a[i], pos);
                    int col = ++array[row][0];
                    array[row][col] = a[i];
                }
                for (int row = 0, i = 0; row < 10; row++) {
                    // 收集过程
                    for (int col = 1; col <= array[row][0]; col++) {
                        a[i++] = array[row][col];
                    }
                    array[row][0] = 0;
                    // 复位，下一个pos时还需使用
                }
            }
        }
        public static void main(String[] args) {
            int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };
            radixSort(a, getMaxWeishu(a));
            for (int i : a)
                  System.out.print(i + " ");
        }
    }