排序算法

发表于 更新于 阅读次数： 本文字数： 556 阅读时长 ≈ 2 分钟

什么是算法

参见维基

  • 输入：一个算法必须有零个或以上输入量。
  • 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
  • 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望通常要求实际运行结果是确定的。
  • 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵 机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
  • 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

算法拥有常见的范式

  • 分治法：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
  • 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
  • 贪婪（心）算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
  • 线性规划法： 考虑多变量寻求各方权衡的最优解。
  • 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。

什么是数据结构

顾名思义，就是指指导数据怎样存储，怎样组织，数据结构通常与算法是联结在一起的的，互不可分的。

常见排序算法

参见维基

每个算法的可视化展示

尽量找时间每个常见排序算法都写一次。

已写的排序算法：

  • 冒泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void bubbleSort(int *p, int length){
    	for(int i=length-1;i>0;i--){
    		for(int j=0,temp=0;j<i;j++){
    			if(p[j] > p[j+1]){
    				temp=p[j];
    				p[j]=p[j+1];
    				p[j+1]=temp;
    			}
    		}
    	}
    }

  • 选择排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void selectionSort(int *p, int length){
    	for(int i=0,temp;i<length-1;i++){
    		temp=i;
    		for(int j=i+1;j<length;j++){
    			if(p[j]<=p[temp]){
    				temp=j;
    			}
    		}
    		if(temp!=i){
    			p[i]=p[i]+p[temp];
    			p[temp]=p[i]-p[temp];
    			p[i]=p[i]-p[temp];	
    		}
    	}
    }

  • 基数排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //实现的不好
    void countingSort(int *p,int length){
    	//假设只会对 [0,100)以内随机数进行排序
    	int *tp =(int*)malloc(100*sizeof(int));
    	for(int i=0;i<100;i++){
    		tp[i]=0;
    	}
    	
    	for(int i=0;i<length;i++){
    		tp[p[i]]++;
    	}
    	
    	for(int j=0,k=0;j<100;j++){
    		while(tp[j] >0){
    			p[k++]=j;
    			tp[j]--;
    		}
    	}
    	free(tp);
    }

  • 堆排序

    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
    void headSort(int *p,int length);
    void makeMaxHead(int *array,int startIndex,int length);

    void headSort(int *array,int length){
        if(length<2){
            return;
        }

        int startIndex=length/2-1;
        for(int  i=startIndex;i>=0;i--){
            makeMaxHead(array,i,length);
        }

        int temp=array[0];
        array[0]=array[length-1];
        array[length-1]=temp;
        headSort(array,--length);
    }

    void makeMaxHead(int *array,int startIndex,int length){
        int iTop;
        int iLeft;
        int iRight;

        while(1){
            iTop=startIndex;
            iLeft=startIndex*2+1;
            int iRight=(startIndex+1)*2;
            if(iLeft<length&&array[iLeft]>array[iTop]){
                iTop=iLeft;
            }
            if(iRight<length&&array[iRight]>array[iTop]){
                iTop=iRight;
            }
            if(iTop!=startIndex){
                int temp =array[iTop];
                array[iTop]=array[startIndex];
                array[startIndex]=temp;
                startIndex=iTop;
            }else{
                break;
            }
        } 
    }