前言

最近这一个月一直都在找实习，准备实习必备的知识点有很多，其中计算机的基础知识尤为重要，技术一面问的问题往往都是一些计算机基础的知识，以下是我在准备面试的过程中整理的一些计算机的基础知识。
这一篇主要是基础的排序算法。

常见的排序算法

冒泡排序

每次将相邻的两个元素进行比较，将较小的元素放到前面。

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

插入排序

每次将一个待排序的记录，按照其关键字的大小插入到前面已经排好序的子序列中的适当位置。

void insertSort(int array[], int count) {
    
    int i, j, k;
    
    for (i = 1; i < count; i++) {
        // 在array[0, i-1]给array[i]上找到合适的位置
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < array[i]) {
                break;
            }
        }
        
        if (j != i - 1) {
            
            int temp = array[i];
            // 将比array[i]大的数据全部后移
            for (k = i - 1; k > j; k--) {
                array[k + 1] = array[k];
            }
            array[k +1] = temp;
        }
    }
}

选择排序

每次从无序区中找出最小的元素，和无序区的第一个元素交换。

void selectSort(int array[], int count) {
    
    for (int i = 0; i < count; i++) {
        
        // 找出最小元素的位置
        int index = i;
        for (int j = i + 1; j < count; j++) {
            
            if (array[j] < array[index]) {
                index = j;
            }
        }
        
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

// 详细版
int quickSortPartition(int array[], int low, int high) {
    
    int i = low, j = high;
    
    // 将第一个元素作为哨兵
    int sentry = array[i];
    
    while (i < j) {
        
        // 从右往左找第一个小于哨兵的元素
        while (i < j && array[j] >= sentry) {
            j--;
        }
        
        if (i < j) {
            array[i] = array[j];
            i++;
        }
        
        // 从左往右找第一个大于哨兵的元素
        while (i < j && array[j] <= sentry) {
            i++;
        }
        
        if(i < j) {
            array[j] = array[i];
            j--;
        }
    }
    
    // 把哨兵放在 i == j 处
    array[i] = sentry;
    
    // 返回哨兵的位置
    return i;
}

void quickSort(int array[], int low, int high) {
    if (low < high) {
        
        // 分界点
        int partition = quickSortPartition(array, low, high);
        // 递归实现
        quickSort(array, low, partition - 1);
        quickSort(array, partition + 1, high);
    }
}

// 简洁版
void quickSort1(int array[], int low, int high) {
    
    int i, j, temp;
    i = low;
    j = high;
    temp = array[low];
    
    if (low > high) {
        return;
    }
    
    while (i != j) {
        
        // 从右往左找第一个小于哨兵的元素
        while (i < j && array[j] >= temp)
            j--;
        
        if (j > i)
            array[i++] = array[j];
        
        // 从左往右找第一个大于哨兵的元素
        while (i < j && array[i] <= temp)
            i++;
        
        if (j > i)
            array[j--] = array[i];
    }
    
    array[i] = temp;
    quickSort1(array, low, i - 1);
    quickSort1(array, i + 1, high);
}

希尔排序

也叫缩小增量排序，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

void shellSort(int array[], int count) {
    
    for (int dk = count / 2; dk > 0; dk = dk / 2) { // 增量
        
        // 直接插入排序
        for (int i = 0; i < dk; i++) {
            
            for (int j = i + dk; j < count; j += dk) {
                
                if (array[j] < array[j - dk]) {
                    
                    int temp = array[j];
                    int k = j - dk;
                    
                    while (k >= 0 && array[k] > temp) {
                        
                        array[k +dk] = array[k];
                        k -= dk;
                    }
                    
                    // 每组最前的一个元素为最小的元素
                    array[k + dk] = temp;
                    
                }
            }
        }
    }
}

归并排序

建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

void merge(int array[], int temp[], int low, int middle, int high) {
    
    int i = low, m = middle, j = middle + 1, n = high;
    int k = 0;
    
    // 那个小就把哪个先放入temp中
    while (i <= m && j <= n) {
        
        if (array[i] < array[j]) {
            temp[k++] = array[i];
        } else {
            temp[k++] = array[j];
        }
    }
    
    while (i <= m) {
        temp[k++] = array[i++];
    }
    while (j <= n) {
        temp[k++] = array[j++];
    }
    
    // 将temp的元素复制到array
    for (int i = 0; i < k; k++) {
        array[low + i] = temp[i];
    }
    
}

void mergeSort(int array[], int temp[], int low, int high) {
    
    if (low > high ) {
        return;
    }
    
    int middle = (low + high) / 2;
    mergeSort(array, temp, low, middle); // 递归左边
    mergeSort(array, temp, middle +1, high); // 递归右边
    merge(array, temp, low, middle, high); // 合并
}

堆排序

算法思想

1. 构造堆
2. 交换堆得末尾元素和根结点
3. 删除末尾结点
4. 依次循环
   因为根结点是堆中最大或最小的元素（取决于构造的是大顶堆还是小顶堆），所以删除得到的序列必是有序的。

void adjustMinHeap(int array[], int i, int count) {
    
    int j, temp;
    
    temp = array[i];
    j = i * 2 +1;
    while (j < count) {
        // 找出较小的子节点
        if (j + 1 < count && array[j +1] < array[j])
            j++;
        
        // 若较小节点比父节点大，直接返回；否则调整节点
        if (array[j] >= temp)
            break;
        
        array[i] = array[j]; // 将较小节点设置为父节点
        i = j;
        j = i * 2 +1;
    }
    
    array[i] = temp;
}

void heapSort(int array[], int count) {
    
    // 构造小顶堆
    for (int i = (count - 1) / 2; i >= 0; i--) {
        adjustMinHeap(array, i, count);
    }
    
    for (int i = count - 1; i >= 1; i--) {
        
        // 交换根节点和最末节点
        int temp = array[i];
        array[i] = array[0];
        array[0] =temp;
        
        // 再次构造小顶堆
        adjustMinHeap(array, 0, i);
    }
}

源代码

本文中所涉及的代码均放在我的Github
传送门BasicSortAlgorithm

最后

本人为iOS开发新手一枚，写的不好的或写错的地方，希望各位大侠能帮忙指正。
各位大侠，如果觉得对自己有点用的，欢迎点个赞，也欢迎大家关注我( Github / 简书 / 微博 / Instagram / 知乎)
谢谢观看此文。