排序算法归类和实现

1.排序算法的分类

image.png

内排序和外排序概念
内排序：指在排序期间数据对象全部存放在内存的排序。
外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。

2.排序算法思想和实现

我们平时面试时遇到的大多数是内排序，现在总结一个内排序各个方法的思想和实现。

（1）直接插入排序法

算法思想：每趟 将一个待排序的元素作为关键字，按照其关键字的大小插入到已经排好的部分序列的适当位置上，直到插入完成。

void InsertSort(int R[],int n){ //待排数据存在R[]中，默认为整型，个数n
        int i,j;
        int temp;
        for(i=2;i<=n;++i){ //数组从下标1 开始存储，第一个元素有序，所以从第二个开始处理
            temp=R[i];  //将待插入元素暂存于temp中
            j=i-1;

            /*下面这个循环完成了从待排元素之前的元素开始扫描，如果大于待排元素，则后移一位*/
            while(j>=1&&temp<R[j]){
                R[j+1]=R[j];
                --j;
            }
            R[j+1]=temp; //找到插入位置，将temp中暂存的待排元素插入
        }

    }

（2）二分法插入排序(也叫折半插入排序)

算法思想：基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同；二分插入排序采用二分法查找插入位置。

        /*** 折半插入排序  */ 
        private static void binaryInsertSort ( int[] array,int n ) { 
           for ( int i = 1; i < n; i++ ){ 
                // if (array[i] > array[i - 1]) // 从大到小 
                if (array[i] < array[i - 1]) { // 从小到大  
                    int tmp = array[i]; 
                    int low = 0; 
                    int high = i - 1; 
                    while (low <= high) { 
                        int mid = ( low + high ) >>> 1;    // if (array[mid] > tmp) // 从大到小 
                        if (array[mid] < tmp){ // 从小到大 
                            low = mid + 1; 
                        } else  { 
                            high = mid - 1; 
                        } 
                    } 
                    for ( int j = i; j > low; j-- ){ 
                        array[j] = array[j - 1]; 
                    } 
                    array[low] = tmp; 
                } 
            } 
        } 

（3）希尔排序

希尔排序又称为缩小增量排序，也属于插入排序类的算法，是对直接插入排序的一种改进。
算法思想：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使用需要排序的数列基本有序，最后再使用一次直接插入排序。

void shellInsert (list R,int n, int h){   //一趟插入排序，h为本趟增量
                int i, j, k;
                for (i = 1; i <= h; i++) {  //i为组号
                    for (j = h; j <= n; j += h) {  //每组从第二个记录开始插入
                        if (R[j].key >= R[j - h].key) continue;  //R[j]大于有序区的最后一个记录，不需要插入
                        R[0] = R[j];
                        k = j - h;
                        do {
                            R[k + h] = R[k];
                            k = k - h;   //后移记录继续向前搜索
                        } while ( k > 0 && R[0].key < R[k].key;);
                        R[k + h] = R[0];
                    }
                }
            }

（4）直接选择排序

算法思想：对n个记录进行扫描，选择最小的记录，将其输出，接着在剩下的n-1个记录中扫描，选择最小的记录将其输出，……不断重复这个过程，直到只剩一个记录为止。

void selectSort(int[] array,int n) {
        int min;
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            min = array[i];
            for (int j = i; j < n; j++) {
                if (array[j] < min) {
                    min = array[j];//最小值
                    tmp = array[i];
                    array[i] = min;
                    array[j] = tmp;
                }
            }
        }
    }

（5）堆排序

堆是一个完全二叉树，树中每个结点对应于原始数据的一个记录，并且每个结点应满足以下条件：非叶结点的数据 大于或等于其左、右孩子结点的数据（若是按从大到小的顺序排序，则要求非叶结点的数据小于或等于其左、右孩子结点的数据）

由堆的定义可看出，其根结点为最大值，堆排序就是利用这一特点进行的。堆排序过程包括两个阶段：
①将无序的数据构成堆（即用无序数据生成满足堆定义的完全二叉树）。
②利用堆排序（即用上一步生成的堆输出有序的数据）。

void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}
 
void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
            return;
        else { //否则交换父子内容再继续子节点和孙节点比较
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
 
void heap_sort(int arr[], int len) {
    int i; //初始化，i从最後一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)  //建堆 ： len/2-1是最后一个非叶子节点位置
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
 
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

（6）冒泡排序

算法思想：
第一个记录和第二个记录比，如果第一个大，则二者交换，否则不交换；然后第二个记录和第三个记录比较，如果第二个大，则交换，否则不交换。。。一直这样进行下去（冒泡排序算法的结束条件是在一趟排序过程中没有发生元素交换）。

void BubblSort(int[], int n){
        int i,j,flag; int temp;
        for (i = n; i >= 2; i--){  //数组从下标1开始存储
            flag = 0;
            for (j = 2; j <= i; ++j){
                if (R[j - 1] > R[j]) {
                    temp = R[j];
                    R[j] = R[j - 1];
                    R[j - 1] = temp; //交换
                    flag = 1;//如果发生交换，flag为1，没有发生交换，值为0
                }
        
                if (flag == 0) {
                    return;
                }
            }
        }
}

（7）快速排序

算法思想：
快速排序使用分治策略来把待排序数据序列分为两个子序列，具体步骤为：

1. 在数据集之中，选择一个元素作为”基准”。
2. 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

void quickSort(int[] arr){
    qsort(arr, 0, arr.length-1);
}
void qsort(int[] arr, int low, int high){
    if (low < high){
        int pivot=partition(arr, low, high);        //将数组分为两部分
        qsort(arr, low, pivot-1);                   //递归排序左子数组
        qsort(arr, pivot+1, high);                  //递归排序右子数组
    }
}
 int partition(int[] arr, int low, int high){
    int pivot = arr[low];     //枢轴记录
    while (low<high){
        while (low<high && arr[high]>=pivot) --high;
        arr[low]=arr[high];             //交换比枢轴小的记录到左端
        while (low<high && arr[low]<=pivot) ++low;
        arr[high] = arr[low];           //交换比枢轴小的记录到右端
    }
    //扫描完成，枢轴到位
    arr[low] = pivot;
    //返回的是枢轴的位置
    return low;
}

（8）归并排序

算法思想：把待排序的文件分成若干个子文件，先将每个子文件内的记录排序，再将已排序的子文件合并，逐个得到完整的排序文件。

    public void mergeSort(int[] a,int left,int right,int n){ //n为数组长度
        if(left<right){
            int middle = (left+right)/2;
            mergeSort(a, left, middle);
            mergeSort(a,middle+1,right);
            merge(a,left,middle,right,n);//合并
        }
    }

    void merge(int[] a, int left, int middle, int right,int n) {
        int [] tmpArray = new int[n];
        int rightStart = middle+1;
        int tmp = left;
        int third = left;
        //比较两个小数组相应下标位置的数组大小，小的先放进新数组
        while(left<=middle&&rightStart<=right){
            if(a[left]<=a[rightStart]){
                tmpArray[third++] = a [left++];
            }else{
                tmpArray[third++] = a[rightStart++];
            }
        }
        //如果左边还有数据需要拷贝，把左边数组剩下的拷贝到新数组
        while(left<=middle){
            tmpArray[third++] = a[left++];
        }
        //如果右边还有数据......
        while(rightStart<=right){
            tmpArray[third++] = a[rightStart++];
        }
        while(tmp<=right){
            a[tmp] = tmpArray[tmp++];
        }
    }

（9）桶排序

将数组分到有限数量的桶里，每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。

 void bucketSort ( int[] array, int min, int max,int n) 
        { 
            int[] tmp = new int[n]; 
            int[] buckets = new int[max - min]; 
            for ( int i = 0; i < n; i++ ) 
            { 
                buckets[array[i] - min]++; 
            } 
            // 从小到大 
            // for ( int i = 1; i < max - min; i++ ) 
            // { 
            // buckets[i] = buckets[i] + buckets[i - 1]; 
            // } 
            // 从大到小 
            for ( int i = max - min - 1; i > 0; i-- ) 
            { 
                buckets[i - 1] = buckets[i] + buckets[i - 1]; 
            } 
            System.arraycopy (array, 0, tmp, 0, n); 
            for ( int k = array.length - 1; k >= 0; k-- ) 
            { 
                array[--buckets[tmp[k] - min]] = tmp[k]; 
            } 
        } 

（10）基数排序（低位优先分配排序法）

基数排序：排序采用的主要数据结构是单链表表示的队列。
算法思想：把排序码分解成若干部分，然后通过对各个部分排序码的分别排序，最终实现对整个排序码的排序。
实现排序的方法：①高位优先法：从最高位排序码 k(0) 开始，逐个针对各个排序码排序。②地位优先法：从最低位排序码 k(d-1) 开始排序

struct Node{
        KeyType key[D];//排序码是数组
        DataType info;
        PNode next;
    }
    
    typedef struct{
        PNode f;//队列头指针
        PNode e;//队列尾指针
       }Queue; //用队列表示各个子序列
    typedef struct Node *RadixList; //待排序文件类型


void radixSort(RadixList *plist,int d,int r){
    int i,j,k; PNode p,head=(*plist)->next;
    final Queue queue[r];//队列数组
    for(j=d-1;j>=0;j--){//进行d次分配和收集
        for(i=0;i<r;i++){
            queue[i].f=queue[i].e=null;//清空队列
        }

        for(p=head;p!=null;p=p->next){
            k=p->key[j]; //按排序码的第j个分量分配
            if(queue[k].f==null){
                queue[k].f=p;//队列为空设队头指针
            }else {
                (queue[k].e)->next=p; //接到队列k尾
            }
            queue[k].e=p;
        }
        
        for(i=0;queue[i].f==null;i++);//找到第一个非空数列
         p=queue[i].e; head =queue[i].f; //head为收集链表的头指针  
        
        for(i++;i<r;i++){
            if (queue[i].f!=null){
                p->next=queue[i].f;
                p=queue[i].e;
            }
        }
        p->next=null;
    }
    
    (*plist)->next=head;
}