排序算法总结

数据结构 + 算法 = 程序

今天闲来没事，我们就来聊一聊几个耳熟能详的排须算法，也算是对自己所学的一个总结。由于个人学识肤浅，难免会有些错误，希望大家积极指出。

1.冒泡排序

相信学过C的人都了解它，这也可能是好多人接触到的第一个排序算法。在实际项目中也是用的非常多的一种排序算法

算法描述

• 比较无序区相邻的元素。如果第一个比第二个大(小)，就就交换它们两个。
• 对无序区的每一对相邻元素做相同的工作，从开始第一对到结尾的最后一对比较完成以后，在无序区最后(前)的元素应该是最大(小)的。
• 每一轮比较都会选出最大(小)的一个数，放在应该无序区的最后(前)，下一轮比较的时候无序区的元素就会减少一个。
• 当所有元素都在有序区的时候，整个排序结束

算法实现(C语言)

void bubbleSortFunction(int *arr, int count) {
    
    for (int i = 0; i < count; i++) {
        
        for (int j = 0; j < count - i - 1; j++) {
            
            if (arr[j] < arr[j+1]) {
                
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

算法分析

• 平均时间复杂度：O(n^2)
• 最好情况时间复杂度：O(n)
• 最坏情况时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 排序方式：In-place
• 稳定性：稳定

算法图解

图片来自网络，如果涉及侵权请告知。

冒泡排序.gif

选择排序

此算法我能唯一想到的好处应该是思想简单不占用额外的内存空间。无论什么数进去都是O(n^2)的时间复杂度，所以在选用它的时候，数据规模越小越好。

算法原理

• 首先在所有元素中找到最大(小)元素，与最前元素交换，此时将所有元素分为有序区元素(最大或最小元素)和无序区元素。
• 在无序区中找到最大(小)元素，与有序区第一个元素交换，此时有序区元素个数加一，无序区元素个数减一。
• 不断重复上一步，直到所有元素全部排序完毕

算法实现(C语言)

void selectionSort(int *arr, int count) {
    
    for (int i = 0; i < count; i++) {
        
        int minIndex = i;
        for (int j = i+1; j < count; j++) {
            
            if (arr[j] < arr[minIndex]) {
                
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

算法分析

• 平均时间复杂度：O(n^2)
• 最好情况时间复杂度：O(n^2)
• 最坏情况时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 排序方式：In-place
• 稳定性：不稳定

算法图解

图片来自网络，如果涉及侵权请告知。

选择排序.gif

插入排序

想想我们在打扑克牌抓拍这个过程，我们就能理解什么是插入排序了。如果你重来没有打过扑克牌，那么我想对你说，为了能很好的理解插入排序这个算法，快去斗一局地主吧。

算法描述

• 在开始排序的时候，第一个元素我们可以认为它已经被排序，并且所有元素被分为有序区元素和无序区元素
• 取出无序区中第一个元素，在有序区从后向前扫描，如果该元素大(小)于所取元素，则将该元素移动到下一个位置；如果该元素不大(小)于所取元素，则将新元素插入到该位置，此时有序区元素个数加一，无序区元素个数减一
• 不断重复上一步，直到所有元素全部在有序区，排序完成

显然上面第二步找到新元素的位置还有很多种算法，比如二分查找，插值查找，斐波那契查找，树表查找，哈希查找。但是查找算法不是本文讨论的重点，因此我们选择最易理解的顺序查找

算法实现(C语言)

void insertSortFunction(int *arr, int count) {
    
    for (int i = 1; i < count; i++) {
        
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] >= temp) {
            
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}

算法图解

图片来自网络，如果涉及侵权请告知。

插入排序.gif

希尔排序

第一个突破O(n^2)的排序算法，是对插入排序的一种改进。

算法描述

• 选择一个增量序列t1...ti...tj...tk,其中ti>tj且tk＝1
• 按增量序列个数k，对序列进行k趟排序
• 每趟排序根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各个子序列进行直接的插入排序。
• 当增量为1时，整个待排序元素作为一个序列来处理。整个排序完成。

算法实现(C语言)

void shellsortFunction(int *arr, int count, int tk) {

    for (int k = 0; k < tk; k++) {
        
        for (int i = 1; k + i * tk < count; i++) {
            
            int temp = arr[k+i*tk];
            int j = k+(i-1)*tk;
            while (j >= k && arr[j] >= temp) {
                
                arr[j+tk] = arr[j];
                j = j - tk;
            }
            arr[j+tk] = temp;
        }
    }
}

算法分析

• 平均时间复杂度：与增量选取有关，一般选去(2^n-1)或(2n+1)
• 最好情况时间复杂度：O(nlgn)
• 最坏情况时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 排序方式：In-place
• 稳定性：不稳定

算法图解

图片来自网络，如果涉及侵权请告知。

希尔排序.gif

归并排序

归并算法是建立在归并操作上的一种有效的排序算法，该算法是分治法的一个典型应用。将已有序的子序合并，得到完全有序的序列。即先使每个子序列有序，在使子序列段间有序。归并排序和选择排序一样性能 不受输入数据的影响时间复杂度始终是O(nlgn)，当然节省了时间就要付出更多空间的代价

算法描述

• 首先将每个元素看成一个子序列，只含有一个元素的子序列必定是有序的
• 将每两个相邻的子序列归并成一个序列
• 不断重复上一步，直到所有序列全部归并成一个序列，排序介绍
• 两个子序列归并原理：申请一个能存放这两个序列的空间形成一个新序列，然后用两个指针分别指向这两个序列的头部，比较两个指针所指元素的大小，将小(大)的放入到新序列中，并且指针向后移动一个元素，直到一个指针所指超出序列，将另一个序列所剩下的元素直接复制到新序列尾部

算法实现(C语言)

void merge(int *left, int countL, int *right, int countR) {
    
    int temp[countL+countR];
    int i = 0, j = 0;
    while (i < countL && j < countR) {
        
        if (left[i] < right[j]) {
            
            temp[i+j] = left[i];
            i++;
        } else {
            
            temp[i+j] = right[j];
            j++;
        }
    }
    for (; i < countL; i++) {
        
        temp[i+j] = left[i];
    }
    for (; j < countR; j++) {
        
        temp[i+j] = right[j];
    }
    for (int i = 0; i < countR+countL; i++) {
        
        left[i] = temp[i];
    }
}

void mergeSort(int *arr, int count) {
    
    if (count > 1) {
        
        int middle = count / 2;
        mergeSort(arr, middle);
        if (count % 2 == 0) {
            
            mergeSort(&arr[middle], middle);
            merge(arr, middle, &arr[middle], middle);
        } else {
            
            mergeSort(&arr[middle], middle+1);
            merge(arr, middle, &arr[middle], middle+1);
        }
    }
}

算法分析

• 平均时间复杂度：O(nlgn)
• 最好情况时间复杂度：O(nlgn)
• 最坏情况时间复杂度：O(nlgn)
• 空间复杂度：O(n)
• 排序方式：Out-place
• 稳定性：稳定

算法图解

图片来自网络，如果涉及侵权请告知。

归并排序.gif

快速排序

快速排序，听名字就知道它存在的意义。它是处理大数据最快的算法之一。通过一趟排序将待排元素分隔成独立的两个部分，其中一部分元素均比另一部分的元素小(大)，然后分别对这两个部分的元素进行快速排序，从而达到整个序列有序的目的

算法描述

• 在待排序列找出一个元素作为基准(一般选择第一个或最后一个)，用这个基准将序列分为3个子序列，分别是大于基准的序列，小于基准的序列和基准。
• 分别对大于基准和小于基准的两个序列进行上一步操作
• 直到不能分为大于基准，小于基准和基准三个子序列为止，排序完成

算法实现

void quickSort(int *arr, int begin, int end) {
    
    if (begin < end && end - begin > 1) {//如果带排序列只有一个元素必定为有序，区间错误无法排序

        int  fontIndex = begin, backIndex = end, standard = arr[backIndex];
        while (fontIndex < backIndex) {//从前扫描的下标等于从后扫描的下标相等的时候，说明此趟排序已经将元素划分为三部分
            
            //将大于基准的元素，尽量放在待排序列的后面
            while (fontIndex < backIndex && arr[fontIndex] < standard) {
                
                fontIndex++;
            }
            if (fontIndex < backIndex) {
                
                arr[backIndex--] = arr[fontIndex];
            }
            //将小于基准的元素，尽量放在待排序列的前面
            while (fontIndex < backIndex && arr[backIndex] > standard) {
                
                backIndex--;
            }
            if (fontIndex < backIndex) {
                
                arr[fontIndex++] = arr[backIndex];
            }
        }
        arr[fontIndex] = standard;//将基准放在小于基准序列和大于基准序列的中间
        quickSort(arr, begin, fontIndex-1);
        quickSort(arr, fontIndex+1, end);
    }
}

void quickSortFunction(int *arr, int count) {
    
    quickSort(arr, 0, count-1);
}

算法分析

• 平均时间复杂度：O(nlgn)
• 最好情况时间复杂度：O(nlgn)
• 最坏情况时间复杂度：O(n^2)
• 空间复杂度：O(lgn)
• 排序方式：In-place
• 稳定性：不稳定

算法图解

图片来自网络，如果涉及侵权请告知。

快速排序.gif

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积四一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的建制或索引总是小(大)于它的父节点。

算法描述

• 对无序的数据先建成一个完全二叉树(将这些无序的元素填充成一颗完全的二叉树，这时一般是不能满足堆的要求的，填充顺序就是按照树的层次遍历顺序，从上倒下，从左到右，一层一层往下放)
• 将这个完全二叉树调整成堆(我们从最后一个非叶子结点开始，如果满足堆的要求，则继续往前看，如果不满足要求，则将此结点与左右孩子结点中最小(大)的互换，如果次此交换破坏了原来已经满足要求的子树，则由此结点向下再度调整)
• 重复上一步，直到这个完全二叉树满足堆的要求
• 输出堆顶元素，然后以最后一个元素来代替堆顶，再次进行调整使之依然是一个堆
• 直到堆中的元素全都输出，整个排序就完成

堆排序可以用二叉树的结构来表示，但是在实际的应用中我问还可以更节省内存，因为完全二叉树的特性我们可以使用数字来简单的表示它。注意在数据量很大的时候数组和二叉树这两种表示法，它们耗用的内存还是有很大差异的

算法实现(C语言)

void heapOne(int *arr, int maxIndex, int index) {
    
    int leftChildIndex = index * 2 + 1;//左孩子在数组中的下标
    int rightChildIndex = index * 2 + 2;//右孩子在数组中的下标
    if (leftChildIndex >= maxIndex && rightChildIndex >= maxIndex) {//已经是叶子结点
        
        return;
    }
    int leftChildValue = INT_MAX;
    int rightChildValue = INT_MAX;
    if (leftChildIndex <= maxIndex) {
        
        leftChildValue = arr[leftChildIndex];
    }
    if (rightChildIndex <= maxIndex) {
        
        rightChildValue = arr[rightChildIndex];
    }
    if (arr[index] < leftChildValue && arr[index] < rightChildValue) {//满足堆的要求
        
        return;
    } else {//找出左右孩子中最大的和它交换,然后继续调整直到满足堆的要求
        
        if (leftChildValue < rightChildValue) {
            
            int temp = arr[index];
            arr[index] = arr[leftChildIndex];
            arr[leftChildIndex] = temp;
            heapOne(arr, maxIndex, leftChildIndex);
        } else {
            
            int temp = arr[index];
            arr[index] = arr[rightChildIndex];
            arr[rightChildIndex] = temp;
            heapOne(arr, maxIndex, rightChildIndex);
        }
    }
}


void heapSortFunction(int *arr, int count) {
    
    for (int i = (count-1)/2; i >= 0; i--) {
        
        heapOne(arr, count-1, i);
    }
    while (count > 0) {
        
        int temp = arr[0];
        arr[0] = arr[count-1];//将堆顶元素用最后一个叶子结点元素代替
        count--;
        heapOne(arr, count, 0);
        arr[count] = temp;//为了节约内存，将堆顶的元素从数组的最后向前逐一放置
    }
}

算法分析

• 平均时间复杂度：O(nlgn)
• 最好情况时间复杂度：O(nlgn)
• 最坏情况时间复杂度：O(nlgn)
• 空间复杂度：O(1)
• 排序方式：In-place
• 稳定性：不稳定

算法图解

图片来自网络，如果涉及侵权请告知。

堆排序.gif

计数排序

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

算法描述

• 首先找出待排序列中最大和最小的元素
• 统计待排序列中值为i的元素出现的次数，存入一个新的数组的第i项
• 对所有的计数累加(重新数组中第一个元素开始，每一项和前一项相加)
• 反向填充目标数组(将每个元素i放在新数组的第Ci项，每放一个元素就将Ci减去1)

算法实现

void countingSortFunction(int *arr, int count) {
    
    if (count > 1) {
        
        int min = arr[0], max = arr[0];
        for (int i = 1; i < count; i++) {//找出最大和最小值
            
            if (arr[i] > max) {
                
                max = arr[i];
            }
            if (arr[i] < min) {
                
                min = arr[i];
            }
        }
        if (min != max) {//所有元素不全部相等
            
            int countArr[max-min+1];
            for (int i = 0; i < max-min+1; i++) {
                
                countArr[i] = 0;
            }
            
            for (int i = 0; i < count; i++) {//计数
                
                countArr[arr[i]-min] += 1;
            }
            int j = 0;
            for (int i = 0; i < max-min+1; i++) {//填充
                
                while (countArr[i] != 0) {
                    
                    arr[j] = min + i;
                    countArr[i] -= 1;
                    j++;
                }
            }
        }
    }
}

算法分析

• 平均时间复杂度：O(n+k)
• 最好情况时间复杂度：O(n+k)
• 最坏情况时间复杂度：O(n+k)
• 空间复杂度：O(k)
• 排序方式：Out-place
• 稳定性：稳定

算法图解

图片来自网络，如果涉及侵权请告知。

计数排序.gif

总结

由于个人能力有限，对于排序算法我也只能列举和总结道这里了。如果大家还知道更加好的排序算法，希望能共享出来相互学习。此篇博客写完，我只想说前辈们用了数年甚至一生苦心专研出来的算法，不管是算法本身还是逻辑思维方法很值得我推敲。身为一个算法学习的托班学生，难免会有所疏忽，欢迎各位批评指点。

[ 相关代码] https://github.com/LHCoder2016/SortAlgorithm.git
[ 欢迎讨论] huliuworld@yahoo.com