iOS + 常用排序算法

算练习吧
参照的原文
常用排序算法总结(一)
八大排序算法

#include <stdio.h>

void printArrayWithRange(int array[], int left, int right){
    for (int i = left; i <= right  ; i++) {
        printf("%d ",array[i]);
    }
    printf("\n");
}

void printArray(int array[], int n){
    printArrayWithRange(array, 0, n-1);
}

void exchange(int *a, int *b){
    if (a==b) {
        return;
    }
    //    // 异或交换
    //    *a ^= *b;   // atemp = a^b
    //    *b ^= *a;   // btemp = a^b^b = a
    //    *a ^= *b;   // atemp = a^b^a = b
    
    //    // 加减法交换
    //    *a = *a + *b;
    //    *b = *a - *b;
    //    *a = *a - *b;
    
    // 中间变量
    int temp = *a;
    *a = *b;
    *b = temp;
}


#pragma mark - 冒泡
/**
  冒泡：相邻对比、交换，最后冒出最大(最小)值；
  稳定性：稳定；
  时间复杂度：O(n^2);
 */
void bubbleSort(int array[], int n){
    for (int i = n ; i > 0 ; i--) { // 待排序个数
        for (int j = 0; j < i - 1; j++) {  // 排序指针
            if (array[j] > array[j+1]) {
                exchange(&array[j], &array[j+1]);
            }
        }
        printArray(array, n);
    }
}

//  冒泡改进：鸡尾酒算法：同时冒泡最大和最小
void cocktailSort(int array[], int n){
    
    int left = 0;
    int right = n-1;
    while (left<right) {
        // 先冒大
        int index = left;
        for (; index < right; index++){
            if (array[index] > array[index+1]) {
                exchange(&array[index], &array[index+1]);
            }
        }
        right --;
        
        // 再冒小
        for (; index > left; index--) {
            if (array[index] < array[index-1]) {
                exchange(&array[index], &array[index-1]);
            }
        }
        left++;
        printArray(array, n);
    }
}

#pragma mark - 选择排序
/**
 选择：每次找到最大(小)，与未排序的第一个数交换；
 稳定性：不稳定；
 时间复杂度：O(n^2);
 */
void selectionSort(int array[], int n){

    int index = 0;
    // 从第一个数开始排，找到比起大的数并交换，指针前移，对后面的数继续排序
    for (int i = 0 ; i < n ; i++) {
        // 比对值
        index = i;
        // 找到最大数
        for (int j = i+1 ; j < n ; j++) {
            if (array[j] > array[index]) {
                index = j;
            }
        }
        // 找到则交换
        if (index != i) {
            exchange(array+i, array+index);
        }
        printArray(array, n);
    }
}

#pragma mark - 插入排序
/**
 直接插入：在未排序的部分拿出一个数，比前面数小(大)则前移，否则处理下个数；
 稳定性：稳定；
 时间复杂度：最好O(n)；最坏、平均O(n^2);
 */
void insertionSort(int array[], int n){

    for (int i = 1 ; i < n ; i++) {
        
        // 挑选出未排序的一个数，准备排序
        int data = array[i];
        
        // 空出来的位置
        int j = i;
        
        // 将比data大的数后移
        while (j > 0 && data < array[j-1]) {
            // 将j的位置空出来
            array[j] = array[j-1];
            j--;
        }
        
        // 插入到正确位置
        array[j] = data;
        printArray(array, n);
    }
}

// 二分插入排序：稳定：在未排序的部分拿出一个数，与排好序的部分采用二分查找分进行对比，找到其位置插入
// 稳定性：稳定；
// 时间复杂度：最好O(nlog2n)；最坏、平均O(n^2);
void binaryInsertionSort(int array[], int n){
    
    int data, left, right, middle;
    
    for (int i = 1 ; i < n ; i++) {
        
        // 挑选出未排序的一个数，准备排序
        data = array[i];
        
        // [0, i-1]为排好序的部分
        left = 0;
        right = i-1;
        
        // 二分查找：left为最终位置
        while (left <= right) {
            middle = (right+left)/2;
            if (data > array[middle]) {
                right = middle-1;
            } else {
                left = middle+1;
            }
        }
        
        // 将left之后的数据往后挪一位
        for (int j = i-1 ; j >= left ; j--) {
            array[j+1] = array[j];
        }
        
        // 插入到正确位置
        array[left] = data;
        printArray(array, n);
    }
    
}

// 希尔排序：递减增量分成小组，进行插入排序，插入排序对有序数组的效率比较高
// 稳定性：不稳定
// 时间复杂度：最好O(n)，平均O(n^1.3)，最坏O(n^2)
void shellSort(int array[], int n){
    
    // 子序列增量
    int incre = n, still = 1;
    
    while(still){
        
        incre /= 2;
        printf("\n\n第一层\n\n");
        // 拆分子序列
        for (int i = 0 ; i < n ; i++) {
            printf("第二层");
            // 单个子序列i，i+incre, i+2*incre, i+3*incre...
            for (int j = i + incre ; j < n ; j += incre) {
                // 子序列采用插入排序
                for(int z = j ; z > i ; z -= incre){
                    if(array[z] < array[z-incre]){
                        int temp = array[z-incre];
                        array[z-incre] = array[z];
                        array[z] = temp;
                        printArray(array, n);
                    } else {
                        printArray(array, n);
                        break;
                    }
                }
            }
        }
        
        if (incre == 1) {
            still = 0;
        }
//        printArray(array, n);
    }
}

#pragma mark - 归并排序
/*
 归并：将数组分成多个小组，将其排好序，再将小组合并
 稳定性：稳定；
 时间复杂度：O(nlog2n);
 */

// 合并数组中排好序的两列［left, middle］和 [middle+1, right]
void merge(int array[],uint left, uint middle, uint right){
    
    // 异常判断
    if ( middle < left || middle >right || right <= left) {
        return;
    }
    
    // left、right只相差1
    if(left+1 == right){
        if (array[left]>array[right]) {
            exchange(array+left, array+right);
        }
        return;
    }
    
    // 临时存储
    int count = right - left + 1, index = 0;
    int *arrayTemp = malloc(sizeof(int)*count);
    for (int i = left; i<=right; i++,index++) {
        arrayTemp[index] = array[i];
    }

    // 合并
    int tempMid = middle - left, tempLeft = 0, tempRight = right - left;
    int i=tempLeft , j=tempMid+1;
    index = left;
    while (i<=tempMid && j<=tempRight) {
        if (arrayTemp[i] < arrayTemp[j]) {
            array[index] = arrayTemp[i];
            i++;
        } else {
            array[index] = arrayTemp[j];
            j++;
        }
        index ++;
    }
    
    //处理尾数
    while (i<=tempMid) {
        array[index] = arrayTemp[i];
        i++;
        index++;
    }
    
    while (j<=tempRight) {
        array[index] = arrayTemp[j];
        j++;
        index++;
    }
    //free(arrayTemp);
}

// 归并：递归
void mergeSortRecursion(int array[], int left, int right){
    // 当left==right时，即为一个数，不执行拆分操作
    if(left<right) {
        
        // 1. 递归对半拆分数组成子序列
        int middle = (left+right)/2;
        // 1.1 左[left, middle]
        mergeSortRecursion(array, left, middle);
        // 1.2 右[middle+1, right]
        mergeSortRecursion(array, middle+1, right);
        
        printf("\n待排\n");
        printArrayWithRange(array, left, right);
        
        // 2. 合并有序的子序列
        merge(array, left, middle, right);
        
        printf("排完一次\n");
        printArrayWithRange(array, left, right);
        printf("最新结果\n");
        printArray(array, right+1);
    }
}

// 归并：非递归：将大问题分割成小问题分别解决
void mergeSortInteration(int array[], int n){
    
    // 按2的幂次方间隔，将数组等分成小组(最后一个小组个数不规则)，相隔两个小组进行归并；
    // 不断更改间隔拆分小组，直到能归成一个小组为止
    // [left,middle,right] [left,middle,right] [left,middle,right] .....
    // 由1个为一组开始拆分
    
    int incre = 1 , left = 0, middle=0, right = 0;
    // incre > n/2 的时候就可以归成一组
    while (incre < n) {
        // 更改间隔后重新归并
        left = 0;
        while (left < n) {
            // 相邻两组归并
            // 界定righ
            right = left+2*incre-1;
            if (right>=n) {
                right=n-1;
            }
            
            // 界定middle
            middle = left+incre-1;
            
            // 合并
            merge(array, left, middle, right);
            
            // 下一组
            left = right+1;
        }
        printf("排完一次\n");
        printArray(array, n);
        
        // 组的个数增大，继续
        incre *= 2;
    }
}

#pragma mark - 快速排序
/**
 快速排序：
 1. 以尾数当基准数，分队，大的在一边(大边)、小的在另一边(小边)，最后可以确定基准数的位置
 2. 小边、大边继续按步骤1处理，
 稳定性：不稳定；
 时间复杂度：最好、平均 O(nlog2n)，最坏 O(n^2);
 空间复杂度：O(nlog2n)
 */
// 快排分组
int partition(int array[], int left, int right){

    int pivot = array[right];       // 基准数
    int separator = left-1;         // separator左边的数小于基准数，右边大于基准数
    
    for (int i = left; i<right; i++) {
        if (array[i] < pivot ){
            separator++;
            exchange(array+i, array+separator);
        }
    }
    
    separator++;
    exchange(array+separator, array+right);
    
    //  separator即基准数的位置
    return separator;
}

// 快排：基准，大的一边、小的另一边，分而治之
// 不稳定：平均：O(nlogn); 最差：O(n^2); 最好：o(nlogn)
void quickSort(int array[], int left, int right){
    
    if (left < right) {
        // 站队，大的一边，小的一边
        int separator = partition(array,left,right);
        // 对小边继续排
        quickSort(array, left, separator-1);
        // 对大边继续排
        quickSort(array, separator+1, right);
    }
}

#pragma mark - 堆排序
/*
 堆排序：选择排序
 1. 将整个数组认为是一个完全二叉树，i的左右节点分别是2*i+1、2*i+2
 2. 建堆：从二叉树最后一个节点的父节点开始调整堆，依次往前
 3. 堆建好后，
    1. 将root元素与堆未元素交换
    2. 获取了一个最大(小)数，由于root元素更换，破坏了堆，需继续调整堆
    3. 堆调整后，重复1,直到剩下两个元素的堆，调整大小
 4. 堆调整：前提是原本是推，由于root元素更换，破坏了堆，需对其进行调整
    1. 与左右子节点比较，是否符合堆的条件，不符合，将更大(小)的元素与堆交换，并记录下被调整堆字节点newRoot
    2. 如果步骤1破坏堆，按步骤1的方式继续调整以newRoot为根的堆
    3. 如果步骤1没有破坏堆，则堆调整好了
 
 稳定性：不稳定；
 时间复杂度：O(nlog2n);
 */

/// 堆调整
void heapAdjust(int array[], int root, int length){
    // 最大堆
    int leftChildIndex = root*2+1;
    int rightChildIndex = root*2+2;
    int newRoot = root;
    
    // 比左节点比较，如果左节点大,则左节点称为root的候选值,
    if (leftChildIndex < length && array[root] < array[leftChildIndex] ){
          newRoot =  leftChildIndex;
    }
    // 将newRoot的值与右节点比较，若右节点大，更换root候选值
    if (rightChildIndex < length && array[newRoot] < array[rightChildIndex] ){
        newRoot =  rightChildIndex;
    }
    
    // root变更，以newRoot为根的堆被破坏，则以newRoot重新调整堆
    if (newRoot != root) {
        exchange(array+newRoot, array+root);
        heapAdjust(array, newRoot, length);
    }
}

/// 建堆
void heapBuild(int array[], int length){
    // 从最后一个元素的父元素开始堆调整
    for (int i = (length-1) / 2; i >= 0; i--) {
        heapAdjust(array, i, length);
    }
}

/// 堆排序
void heapSort(int array[], int length){
    heapBuild(array, length);
    for (int i = 0; i < length; i++) {
        // 末尾数与堆顶交换，并重新调整堆；
        exchange(array, array+length-i-1);
        heapAdjust(array, 0, length-i-1);
    }
}

int main(int argc, const char * argv[]) { 
    int array[] = {2, 6, 0, 9, 7, 5, 8, 1, 4, 3, 43, 10, 4, 49, 89, 56,2, 45,75, 23,54,7,45,97,23,65,32,54,23};
    int count = sizeof(array)/sizeof(int);
    heapSort(array, count);
    printArray(array, count);
    return 0;
}