经典排序算法的C++实现

DjangoBUAA

1、冒泡排序  O(n2)
每一次把最大的移动到最右端，第一次从0~n-1中找到最大的放到n-1处，第二次从0~n-2中找到最大的放到n-2处……

classBubbleSort {
public:
    int* bubbleSort(int* A, intn) {
        inti,j,temp = 0;
        for(i = 1;i < n;i++)
            for(j = 0; j < n - i;j++) {
            if(A[j] > A[j + 1]) {
                temp = A[j + 1];
                A[j + 1] = A[j];
                A[j] = temp;
            }
        }
        returnA;
    }
};
2、选择排序  O(n2)
先把0处的看作最小值，从1~n-1中找到比它小的值，交换；再把1处的看作最小值，从2~n-1中找到比他小的，交换；……
classSelectionSort {
public:
    int* selectionSort(int* A, intn) {
        if(n == 0) returnA;
        inti,j,min = 0,temp;
        for(i = 0;i < n;i++) {
            min = i;
            for(j = i+1;j < n;j++) {
                if(A[j] < A[min]) {
                    min = j;
                }
            }
           temp = A[i];
           A[i] = A[min];
           A[min] = temp;                    
        }      
        returnA;
    }
};

3、插入排序  O(n2)
先把0处看作已排序的序列，将1~n-1处逐个地与0处比较，若比0处小，则将其插入到已排序的序列中；……；假设0~3已排序，将4~n-1处依次与3处比较，若小于3处，则将其插入到0~3的适当位置；……
classInsertionSort {
public:
    int* insertionSort(int* A, intn) {
        inti,j,k,temp;
        for(i = 1;i < n;i++) {
            k = i;
            for(j = i-1;j >=0;j--) {
            if(A[k] < A[j]) {
                temp = A[k];
                A[k] = A[j];
                A[j] = temp;
                k = j;
            }               
            }                     
        }
         returnA;  
    }
};

4、归并排序（递归）  O(NlogN)
先将序列分成2个子序列，再分成4个，……，直到所有子序列都只含一个元素；对每个子序列排序，再将相邻的两个已排序子序列归并为一个排序序列，依次类推，最后归并出原序列的排序序列。
classMergeSort {
public:

    voidMerge(int* A,intstart,intmiddle,intend) {
        inttemp[end-start +1];
        intk = 0;
        for(inti = start,j = middle + 1;i <= middle || j <= end;k++) {
            if(i <= middle && j <= end) {
                if(A[i] < A[j]) {
                temp[k] = A[i];
                i++;
            }
            else{
                temp[k] = A[j];
                j++;
            }
            }
            elseif(i <= middle) {
                temp[k] = A[i];
                i++;
            }
            else{
                temp[k] = A[j];
                j++;
            }
                     
        }
        for(intm = 0;m < k;m++)
            A[start + m] = temp[m];
    }
    voidDivide(int* A,intstart,intend) {

        if(start < end) {
            intm = (start + end)/2;
            Divide(A,start,m);
            Divide(A,m+1,end);
            Merge(A,start,m,end);
        }
      
    }
    int* mergeSort(int* A, intn) {
        Divide(A,0,n-1);
        returnA;
    }
};

5、快速排序（递归）  O(NlogN)
先从序列中选取一个元素为基数，一般选最左边一个；两个指针i、j分别从序列的头尾向中间遍历；j从右到左找到小于基数的元素（j处），复制到基数处（i处），i++；然后i从左向右找到大于基数的元素（i处），复制到j处，j--；依次类推，直到i与j相遇使i>=j，while循环结束，此时已把序列分成左右两个子序列，左边小于基数，右边大于基数；再将左右子序列当做未排序序列进行递归。
class QuickSort {
public:
    void Quick(int* A,int start,int end) {
        if (start >= end) return;
        else {
            int i = start,j = end;
            int base = A[i];
            while (i < j) {
                while (i < j && A[j] > base) j--;
                if (i < j) {
                    A[i] = A[j];
                    i++;
                }
                while (i < j && A[i] < base) i++;
                if (i < j) {
                    A[j] = A[i];
                    j--;
                }
            }
            A[i] = base;
            Quick(A,start,i - 1);
            Quick(A,i + 1,end);
        }
    }
    int* quickSort(int* A, int n) {
        // write code here
        Quick(A,0,n-1);
        return A;
    }
};

6、堆排序 O（NlogN）
堆实际上是一种思想，不是一种数据存储结构，堆中数据的逻辑结构与完全二叉树一样，设总共有n个结点，则叶结点个数为n+1/2或者n/2，则非叶子结点个数为n-1/2或者n/2，当n能被2整除时为n/2，不能被整除时为n-1/2。
思路：
（1）堆化数组。给定一个长度为n的乱序数组，若要递增排序，则先将其堆化（按层序存储），即把原数组调整为大端堆。
（2）取堆顶元素放入数组末尾。每次将堆顶元素与数组末尾元素交换。
（3）调整交换元素后的堆。再从堆顶到第n-2个元素调整数组为大端堆，直到n-2=1为止，即堆中只剩下一个元素未放入排序序列为止。
classHeapSort {
public:
     
    void heapify(int* A,inti,intn) {
        intj,temp;
        temp = A[i];
        j = 2*i + 1;
         
        while(j < n) {
            if(j + 1< n && A[j+1] > A[j]) j++;
            if(A[j] <= temp) break;
                A[i] = A[j];
                i = j;
                j = 2*i +1;

        }
        A[i] = temp;
        return;
    }
     
    int* heapSort(int* A, intn) {
        // write code here
        int temp;
        for(int m = n/2- 1;m >= 0;m--)
            heapify(A,m,n);
        for(int k = n-1;k >= 1;k--) {
            temp = A[k];
            A[k] = A[0];
            A[0] = temp;
            heapify(A,0,k);
        }
        return A;
    }
};


7、希尔排序 O(NlogN)
插入排序的改进。每一次比较的步长是变化的。例如，长度为n的数组，第一次设置步长为n/2，认为前n/2个数已经排序，从第n/2+1个开始，将其逐个与第1个、2个……比较，大于则交换，小于则不做操作。然后减小步长，继续以上步骤直到步长变为1.
classShellSort {
public:
    int* shellSort(int* A, intn) {
        // write code here
        intspan = n/2;
        inti,j,temp;
         
        while(span >= 1) {
            for(i = span;i < n;i++) {
                j = i - span;
                while(j >= 0) {
                    if(A[j] > A[i]) {
                        temp = A[j];
                        A[j] = A[i];
                        A[i] = temp;                        
                    }
                    j -= span;
                }
            }
            span--;
        }
        returnA;
    }
};

8、计数排序 O(N)
（1）先确认待排序数组A元素的取值范围，相当于找出最大值max和最小值min，桶C的大小必须要能包含所有的元素。
（2）顺序遍历数组A，把A[i]与桶C的下标对应起来，即，将C[A[i]-min]加1。这样A最小的元素与C的第一个下标对应，最大元素与C的最后一个下标对应。这个过程相当于把A中元素装入对应的桶中。
（3）顺序遍历桶C，把桶中元素按顺序倒出来，就是从小到大的已排序序列。
classCountingSort {
public:
    int* countingSort(int* A, intn) {
        // write code here
        intmax = A[0],min = A[0];
        for(inti = 0;i < n;i++) {
            if(A[i] > max) max = A[i];
            if(A[i] < min) min = A[i];
        }         
        intsizeC = max - min + 1;
        int*C = newint[sizeC];
        for(inti = 0;i < sizeC;i++)
            C[i] = 0;         
        for(intj = 0;j < n;j++) {
            C[A[j]-min]++;
        }
        intz = 0;
        for(intm = 0;m < sizeC;m++) {
            while(C[m] > 0) {
                A[z] = m + min;
                z++;
                C[m]--;
            }            
        }
        delete []C;
        returnA;
    }
};

9、基数排序 O(N)
先根据个位把各元素入桶，把桶中元素倒出来得到按个位排序的序列；再按照十位把各元素入桶，倒出来得到按十位排序的序列；以此类推……
注：A中数据小于2000.
一维数组实现：
classRadixSort {
public:
    int* radixSort(int* A, intn) {
        // write code here
        intC[10];
        intdivisor[5] = {1,10,100,1000,10000};
        int*B = newint[n];
        for(inti = 0;i < 4;i++) {
            for(intj = 0;j < 10;j++)
                C[j] = 0;
            for(intk = 0;k < n;k++) {
                intunit = (A[k]%divisor[i+1])/divisor[i];
                C[unit]++;
            }
            for(intj = 1;j < 10;j++)
                C[j] += C[j-1];
            
            for(intk = n-1;k >= 0;k--) {
                intunit = (A[k]%divisor[i+1])/divisor[i];
                B[C[unit]-1] = A[k];
                C[unit]--;
            }
            for(intj = 0;j < n;j++)
            A[j] = B[j];         
        }
        delete []B;
        B = NULL;
        returnA;
    }
};

二维数组实现：
class RadixSort {
public:   
int* radixSort(int* A, int n) {
        // write code here
        vector<deque<int> > bucket(10);
        int divisor[] = {1,10,100,1000,10000};
        for (int i = 0;i < 4;i++) {
            for (int j = 0;j < n;j++) {
                int unit = (A[j]%divisor[i+1])/divisor[i];
                bucket[unit].push_back(A[j]);
            }
            for (int j = 0, k = 0;j < 10;j++) {
                while (!bucket[j].empty()) {
                    A[k++] = bucket[j].front();
                    bucket[j].pop_front();
                }
            }
        }
        return A;
    }
};
10、小范围排序
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。
选择改进的堆排序。根据题意，最小值一定在A的前k(0~k-1)个元素内、次小值一定在A的第二组k(1~k)个元素内，以此类推，每次取原数组A的k个元素进行堆排序，然后把堆顶元素放入A的已排序序列中，(0~k-1)排序的堆顶赋值给A[0]，(1~k)排序的堆顶赋值给A[1]，以此类推。最后剩下A中最后的k个元素(k-n~n-1)，进行标准的堆排序，第一次是K个元素的堆，排序后将堆顶赋值给A[n-k]，紧接着把堆尾元素赋值给堆顶，再排序，此时只是k-1个元素的堆，依次类推，每次把堆顶元素放入A中已排序序列后，都把堆尾元素赋值到堆顶，同时堆的元素个数减1，直到堆的元素个数为1，整个排序结束。
class ScaleSort {
public:
void heapify(int* B,int i,int k) {
        int j,ex;
        ex = B[i];
        j = 2*i + 1;
        while (j < k) {
            if (j + 1 < k && B[j + 1] < B[j])
                j++;            
            if (B[j] >= ex) break;           
            B[i] = B[j];
            i = j;
            j = 2*i + 1;
        }
        B[i] = ex;
        return;
    }

    vector<int> sortElement(vector<int> A, int n, int k) {
        // write code here
        int m = 0,exc;
       int *temp = new
       int[k];
        for (int l = 0;l < k;l++) {
            temp[l] = A[l];
        }
        for (int i = k/2-1;i >= 0;i--)
        heapify(temp,i,k);

        for (int i = k;i < n;i++) {
            A[i-k] = temp[0];
            temp[0] = A[i];
            heapify(temp,0,k);
        }

        for (int j = n-k;j < n;j++) {
            A[j] = temp[0];
            k--;
            temp[0] = temp[k];
            heapify(temp,0,k);
        }

        delete []temp;
        temp = NULL;
        return A;
    }
};

11、求一个数组排序后相邻元素之差的最大值，时间复杂度为O（n）、空间复杂度为O（n）
若先排序后求差值则只有桶排序满足时间复杂度，但是桶排序不能满足空间复杂度，桶排序的空间复杂度为O(max-min)。因此要用改进的桶排序但是又没有真正的排序。

①、求出数组A的最大值max和最小值min，并把区间max-min平均分成n份，每份大小为interval，则只需要n+1个桶;
②、用A[i]-min/interval的整数部分确定A[i]该入的桶，并定义三个大小为n+1的数组，bucket记录n+1个桶每个桶的入桶元素个数，max_bucket记录每个桶中最大值，min_bucket记录每个桶中最小值；
③、遍历bucket数组，将后一个桶的最小值min_bucket[j]减去前一个桶的最大值max_bucket[j-1]，记录下最大的差值，返回该差值。

class Gap {
public:
    int maxGap(vector<int> A, int n) {
        int max = A[0],min = A[0];

        for (int i = 1;i < n;i++) {
            if (A[i] > max) max = A[i];
            else
                if (A[i] < min) min = A[i];
        }

        float interval = (float)(max - min)/n;

        int bucket[n+1];
        for (int j = 0;j < n+1;j++)
            bucket[j] = 0;

        
int max_bucket[n+1],min_bucket[n+1];

        for (int i = 0;i < n;i++) {
            int j = (int)(A[i]-min)/interval;
            bucket[j]++;
            min_bucket[j] = A[i];
            max_bucket[j] = A[i];
        }

        for (int i = 0;i < n;i++) {
            int j = (int)(A[i]-min)/interval;
            if (A[i] > max_bucket[j]) max_bucket[j] = A[i];
            if (A[i] < min_bucket[j]) min_bucket[j] = A[i];
        }

        int maxGap = 0;
        for (int i = 0,j = 1;j < n+1;j++) {
            if (bucket[j] > 0) {
                if (min_bucket[j]-max_bucket[i] > maxGap)
                    maxGap = min_bucket[j] - max_bucket[i];
                i = j;
            }               
        }
        return maxGap;
    }
};