排序(新排版)

冒泡排序

void bubbleSort(int a[], int count) {
    int temp = 0;

    if (a == NULL) return;
    if (!count) return;

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

插入排序

void insertSort(int a[], int count) {
    int i = 1, j = 0;
    int temp = 0;

    for (; i<count; i++) {
        j = i;
        temp = a[i];
        while(j>0 && temp < a[j-1]) {
            a[j] = a[--j]; 
        }
        if (i != j) {
            a[j] = temp;
        }
    }
}

二分插入排序

void binaryInsertSort(int a[], int count) {
    int i, j;
    int left, middle, right, temp = 0;
    
    if (!a || count <= 0) return;
    for (i=1; i<count; i++) {
        j = i, temp = a[i];
        left = 0, right = i-1;
        
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (a[middle] <= temp) {
                left = middle + 1;
            }
            else {
                right = middle - 1;
            }
        }

        while (j>left) {
            a[j] = a[--j];
        }
        a[j] = temp;
    }
}

希尔排序

void shellSort(int a[], int count) {
    int stepLength = count / 2;
    int i, j, k;
    
    if (!a || count <= 0) return;
  
    while(stepLength) {
         for (i=0; i<stepLength; i++) {
             for(j=i+stepLength; j<count; j+=stepLength) {
                 k = j;
                 temp = a[k];
                 
                 while(k>= stepLength && temp < a[k-stepLength]) {
                       a[k] = a[k-stepLength];
                       k -= stepLength;
                  }

                if (k != j) a[k] = temp;
             }
        }      

        stepLength /= 2;
    }
}

选择排序

void selectSort(int a[], int count) {
    int i, j;
    int temp, minIndex = 0;

    for (i=0; i<count ; i++) {
        temp = a[i];
        minIndex = i;
        for (j=i+1; j<count; j++) {
            minIndex = a[minIndex] < a[j] ? j : minIndex;
        }

        if (minIndex != i) {
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

快速排序

void quickSort(int a[], int count) {
    if (!a || !count) return;
    _quickSort(a, 0, count-1);
}

void _quickSort(int a[], int beginIndex, int endIndex) {
    int i = beginIndex, j = endIndex;
    int flag = 0;

    flag = a[beginIndex];

    if (beginIndex >= endIndex) return;

    while(i<j) {
        while(i<j && a[i]<flag) { i++; }
        while(j>i && a[j]>flag) { j--; }

        if (i<j) {
            a[i] = a[j] ^ a[i];
            a[j] = a[i] ^ a[j];
            a[i] = a[j] ^ a[i];
        }
    }

    if (start < i) {
        _quickSort(a, start, i-1);
    }
    if (end > j) {
        _quickSort(a, j+1, end);
    }
}