WOJ Problem 1170 Sorting

发表于   |   分类于

Description

对一组输入的数据进行排序。
对输入的数据，我们有如下的约定：所有的输入数据都为正整数，且都不大于300000000。但是输入的数据可能会有重复，排序时，应将重复的数据合并，即同样的数只处理一次。

Input

只有一组数据，以0结尾。

Output

输出排序后的数据（不含0），其中相同的数应只显示1个。

Sample Input

12500000 10000000 12500000 0

Sample Output

10000000 12500000

Hint

woj中的一个5分题，本以为会有一些技巧，尝试了桶排序（超空间）、位排序（超时间）、最后发现只需要普通的快排即可

QuickSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h> 
#define N 300000000
int comp(const void*a,const void*b)//用来做比较的函数。
{
    return *(int*)a-*(int*)b;
}
 
int main()
{
    	int array=(int *)malloc(30000000sizeof(int)); 
 		int gt=0,count=0;
 		while(scanf("%d",&gt)&&gt!=0)
         {
            array[count]=gt;
            count++;
		}
		qsort(array,count,sizeof(int),comp);//调用qsort排序
 		int prev=0;
 		for(int i=0;i<count;i++)
 		{
 			if(array[i]==prev)
 			continue;
 			else
 			{
 				printf("%d ",array[i]);
 				prev=array[i];
 			}
 		
 		}
 		return 0;
}

快速排序一般写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}
void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int partition(int a[], int low, int high)
{
	int privotKey = a[low];					//基准元素
	while(low < high){				//从表的两端交替地向中间扫描
		while(low < high  && a[high] >= privotKey) --high;  
	//从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
		swap(&a[low], &a[high]);
		while(low < high  && a[low] <= privotKey ) ++low;
		swap(&a[low], &a[high]);
	}
	print(a,10);
	return low;
}

void quickSort(int a[], int low, int high){
        if(low < high){
        int privotLoc = partition(a,  low,  high);  //将表一分为二
            quickSort(a,  low,  privotLoc -1);            //递归对低子表递归排序
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序
    }
}

int main(){
    int a[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<"初始值：";
    print(a,10);
    quickSort(a,0,9);
    cout<<"结果：";
    print(a,10);

}

BucketSort

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 300000000
//超空间  桶排序 
int main()
{
    int gt;
    int *array=(int *)malloc(N*sizeof(int));
    memset(array,0,N);
    int i=0,max=0;
    while(scanf("%d",&gt)!=EOF&&gt!=0)
    {
        array[gt]=gt;
        i++;
    }
    for(int j=1;j<N;j++)
    {
        if(array[j]!=0)
        printf("%d ",array[j]);
    }
    return 0;
}

BitSort

#include <stdio.h>
#define N 300000000
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F

//超时间，bitsort 

int arr[1+ N/BITSPERWORD];

void set(int i)
{
    arr[i>>SHIFT] |= (1<<(i&MASK));
}    

int test(int i)
{
    return arr[i>>SHIFT] & (1<<(i&MASK));
}

int main()
{


    int gt=0,max=0;
    //int i=0,max=0;
    while(scanf("%d",&gt)&&gt!=0)
    {
        if(gt>max)
        max=gt;
        set(gt);    
    }
    for(int j=1;j<max;j++)
    {
        if (test(j))
        printf("%d ",j);
    }
    printf("%d",max);
    return 0;
}

HeapSort

/*与题目无关，作为参考
*/

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}



/**
 * 已知H[s…m]除了H[s] 外均满足堆的定义
 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
 *
 * @param H是待调整的堆数组
 * @param s是待调整的数组元素的位置
 * @param length是数组的长度
 *
 */
void HeapAdjust(int H[],int s, int length)
{
    int tmp  = H[s];
    int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    while (child < length) {
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            ++child ;
        }
        if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child;         // 重新设置s ,即待调整的下一个结点的位置
            child = 2*s+1;
        }  else {             // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
             break;
        }
        H[s] = tmp;            // 当前待调整的结点放到比其大的孩子结点位置上
    }
    print(H,length);
}


/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{ 
    //最后一个有孩子的节点的位置 i=  (length -1) / 2
    for (int i = (length -1) / 2 ; i >= 0; --i)
    HeapAdjust(H,i,length);
}
/**
 * 堆排序算法
 */
void HeapSort(int H[],int length)
{
    //初始堆
    BuildingHeap(H, length);
    //从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {
        //交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i]; H[i] = H[0]; H[0] = temp;
        //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H,0,i);
  }
} 

int main(){
    int H[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<"初始值：";
    print(H,10);
    HeapSort(H,10);
    //selectSort(a, 8);
    cout<<"结果：";
    print(H,10);

}

Bubble Sort

void bubbleSort(int a[], int n){
    for(int i =0 ; i< n-1; ++i) {
        for(int j = 0; j < n-i-1; ++j) {
            if(a[j] > a[j+1])
            {
                int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
            }
        }
    }
}

/*
*/

void Bubble_1 ( int r[], int n) {
int i= n -1;  //初始时,最后位置保持不变
while ( i> 0) { 
    int pos= 0; //每趟开始时,无记录交换
    for (int j= 0; j< i; j++)
        if (r[j]> r[j+1]) {
            pos= j; //记录交换的位置 
            int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
        } 
        i= pos; //为下一趟排序作准备
     } 
}  

void Bubble_2 ( int r[], int n){
    int low = 0; 
    int high= n -1; //设置变量的初始值
    int tmp,j;
    while (low < high) {
        for (j= low; j< high; ++j) //正向冒泡,找到最大者
                if (r[j]> r[j+1]) {
                    tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
                } 
        --high;                    //修改high值, 前移一位
        for ( j=high; j>low; --j) //反向冒泡,找到最小者
            if (r[j]<r[j-1]) {
                tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
            }
        ++low;                    //修改low值,后移一位
    } 
}

Merge Sort

void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
    int j,k;
    for(j=m+1,k=i; i<=m && j <=n ; ++k){
        if(r[j] < r[i]) rf[k] = r[j++];
        else rf[k] = r[i++];
    }
    while(i <= m)  rf[k++] = r[i++];
    while(j <= n)  rf[k++] = r[j++];
}

归并的迭代算法

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
    int j,k;
    for(j=m+1,k=i; i<=m && j <=n ; ++k){
        if(r[j] < r[i]) rf[k] = r[j++];
        else rf[k] = r[i++];
    }
    while(i <= m)  rf[k++] = r[i++];
    while(j <= n)  rf[k++] = r[j++];
    print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ 
    int len = 1;
    ElemType *q = r ;
    ElemType *tmp ;
    while(len < lenght) {
        int s = len;
        len = 2 * s ;
        int i = 0;
        while(i+ len <lenght){
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
            i = i+ len;
        }
        if(i + s < lenght){
            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
        }
        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf
    }
}


int main(){
    int a[10] = {3,1,5,7,2,4,9,6,10,8};
    int b[10];
    MergeSort(a, b, 10);
    print(b,10);
    cout<<"结果：";
    print(a,10);

}

归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)
{ 
    ElemType *rf2;
    if(s==t) r[s] = rf[s];
    else
    { 
        int m=(s+t)/2;            /*平分*p 表*/
        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/
        MSort(r, rf2, m+1, t);        /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
        Merge(rf2, rf, s, m+1,t);    /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
    }
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{   /*对顺序表*p 作归并排序*/
    MSort(r, rf,0, n-1);
}

#Radix Sort

基数排序

Void RadixSort(Node L[],length,maxradix)
{
   int m,n,k,lsp;
   k=1;m=1;
   int temp[10][length-1];
   Empty(temp); //清空临时空间
   while(k<maxradix) //遍历所有关键字
   {
     for(int i=0;i<length;i++) //分配过程
    {
       if(L[i]<m)
          Temp[0][n]=L[i];
       else
          Lsp=(L[i]/m)%10; //确定关键字
       Temp[lsp][n]=L[i];
       n++;
   }
   CollectElement(L,Temp); //收集
   n=0;
   m=m*10;
  k++;
 }
}

Select Sort

void print(int a[], int n ,int i){
    cout<<"第"<<i+1 <<"趟 : ";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
/**
 * 数组的最小值
 *
 * @return int 数组的键值
 */
int SelectMinKey(int a[], int n, int i)
{
    int k = i;
    for(int j=i+1 ;j< n; ++j) {
        if(a[k] > a[j]) k = j;
    }
    return k;
}

/**
 * 选择排序
 *
*/
void selectSort(int a[], int n){
    int key, tmp;
    for(int i = 0; i< n; ++i) {
        key = SelectMinKey(a, n,i);           //选择最小的元素
        if(key != i){
            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
        }
        print(a,  n , i);
    }
}
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    cout<<"初始值：";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl<<endl;
    selectSort(a, 8);
    print(a,8,8);
}

单选择排序的改进——二元选择排序

void SelectSort(int r[],int n) {
    int i ,j , min ,max, tmp;
    for (i=1 ;i <= n/2;i++) {  
        // 做不超过n/2趟选择排序 
        min = i; max = i ; //分别记录最大和最小关键字记录位置
        for (j= i+1; j<= n-i; j++) {
            if (r[j] > r[max]) { 
                max = j ; continue ; 
            }  
            if (r[j]< r[min]) { 
                    min = j ; 
            }   
      }  
      //该交换操作还可分情况讨论以提高效率
      tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
      tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 

    } 
}

Summary

Referrence

八大排序算法

-------------本文结束 感谢您的阅读-------------
作者：GonewithGt
有问题请 留言 或者私信我的 微博。
满分是10分的话，这篇文章你给几分