软件开发-理论性知识（二）

墨蓝 2022-09-18 02:00 178阅读 0赞

1.算法之堆排序算法

/**
     * 大根堆，从小到大排序
     * 
     * JAVA代码实现
     * 
     */
    public class HeapSorter {
    	private static int N = 10000000;
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		int[] arr = new int[N + 1];
    		for (int i = 0; i <= N; i++) {
    			arr[i] = ((Double) (Math.random() * 1000)).intValue();
    		}
    		initHeap(arr, N);
    		System.out.println("init check's result is " + checkInit(arr));
    		doSort(arr);
    		System.out.println("result check's result is " + checkResult(arr));
    	}
    
    	private static boolean checkInit(int[] arr) {
    		boolean result = true;
    		for (int i = 1; i <= N; i++) {
    			result = result && isHeap(arr, i, N);
    		}
    		return result;
    	}
    
    	private static boolean checkResult(int[] arr) {
    		boolean result = true;
    		for (int i = 1; i <= N - 1; i++) {
    			result = result && (arr[i] <= arr[i + 1]);
    		}
    		return result;
    	}
    
    	private static void doSort(int[] arr) {
    		int maxIndex = N;
    		while (maxIndex > 0) {
    			arr[0] = arr[maxIndex];
    			arr[maxIndex] = arr[1];
    			arr[1] = arr[0];
    			maxIndex--;
    			buildHeap(arr, 1, maxIndex);
    		}
    	}
    
    	private static void initHeap(int[] arr, int maxIndex) {
    		for (int p = maxIndex / 2; p >= 1; p--) {
    			buildHeap(arr, p, maxIndex);
    		}
    	}
    
    	private static boolean isHeap(int[] arr, int i, int maxIndex) {
    		boolean result = false;
    		if (i > maxIndex / 2) {
    			result = true;
    		} else {
    			if (arr[i] >= arr[2 * i]
    					&& ((2 * i + 1 > maxIndex) || arr[i] >= arr[2 * i + 1])) {
    				result = true;
    			}
    		}
    		return result;
    	}
    
    	private static void buildHeap(int[] arr, int p, int maxIndex) {
    		if (!isHeap(arr, p, maxIndex)) {
    			int larger = p * 2;
    			if (p * 2 + 1 <= maxIndex && arr[p * 2] < arr[p * 2 + 1]) {
    				larger = p * 2 + 1;
    			}
    			arr[0] = arr[larger];
    			arr[larger] = arr[p];
    			arr[p] = arr[0];
    			buildHeap(arr, larger, maxIndex);
    		}
    	}
    
    }

//program name	: heap sort （C代码实现）
    //author		: Dam
    //email			: zhq651@126.com
    //discription	: This is a sort that fits for find max or min key from huge data;
    // The tree mentioned before is binary tree.And it is not stabled.
    // step 1:build a heap
    // step 2:delete the root node;
    // step 3:rebuild the heap by using the left nodes
    // step 4:loop step 2 and step 3,until there is no node left.
    //space & time:
    // space: S(n)= O(1)
    // time:  T(n)= nlog(2,n)
    
    
    #include <stdio.h>
    #include <time.h>
    
    #define FALSE 0
    #define TRUE 1
    #define NUMMAX 1000000
    
    typedef struct hs_data
    {
    	unsigned int key;
    	char value[30];
    	
    }ListType, *pListType;
    
    int print_set(ListType lt[],unsigned int n);
    int hs_sift(ListType r[],int k,int n);
    int getNTopValue(ListType lt[],int n);//Sub HeapSort - unprogramed.
    int HeapSort(ListType r[], int n);
    
    // heap sort in sequent order 
    int hs_sift(ListType r[],int k,int n)
    {
       	int i=k,j=2*i+1,finished= FALSE;
       	unsigned int x=r[k].key;
       	
       	ListType t = r[k];
      	while((j<n)&&(!finished))
      	{
      		//find the smaller child from the left and right children,
      		//find the bigger one,if in inverted sequent order
      		if ((j<n-1) && (r[j].key > r[j+1].key))     
    			j++;
    			
      		if (x <= r[j].key)
    			finished= TRUE;
     		else 
     		{
     			r[i]= r[j];
     			i= j;
     			j= 2*i+1;
     		}
     	}
     	
     	r[i]= t;
     	
     	return 0;
    }
    
    
    
    // This algs needs one place;
    int HeapSort(ListType r[], int n)
    {
    	int i;
    	
    	//build the heap
    	//loop every unleaf node,and compare it with its children,grand...children.
    	for(i=(n-1)/2; i >= 0; i--)
    		hs_sift(r, i, n);
    	
    	//printf("after build deap!\n");
    	//print_set(r,n);
    	
    	//delete the root node from heap,then rebuild the heap,until there no node left
    	for(i=n-1; i > 0; i--)
    	{
    		//replace the root node using the last node,then resort it
    		ListType t;
    		t   = r[0];
    		r[0]= r[i];
    		r[i]= t;
    
    		hs_sift(r, 0, i);
    	}
    	
    	//printf("after deap sort!\n");
    	//print_set(r,n);
    	return 0;
    }
    
    
    // print the result in before sorting and after sorting 
    int print_set(ListType lt[],unsigned int n)
    {
    	printf("=====================================\n");
    	printf("start print....\n");
    	int i=0;
    	while(i < n )
    	{
    		printf("%u\n", lt[i].key);
    		i++;
    	}
    
    	printf("print end ....\n");
    	printf("=====================================\n");
    	
    	return 0;
    }
    
    
    int main(void)
    {
    	ListType big_set[NUMMAX+1];
    	int i;
    	
    	//init the rander with different seeds;
    	srand(time(NULL));
    	
    	for( i=0; i < NUMMAX; i++)
    	{
    		ListType t;
    		memset(&t,'\0', sizeof(ListType));
    		t.key=rand()%(NUMMAX); 
    		//t.key=(unsigned int)(10-i);
    		strcpy(t.value, "");
    		
    		big_set[i]= t;
    	}
    	
    	printf("before sorting,the set is :\n");
    	print_set(big_set, NUMMAX);
    	
    	HeapSort(big_set, NUMMAX);
    	
    	printf("after sorting, the set is :\n");
    	print_set(big_set, NUMMAX);
    	
    	return 0;
    }

1)实现思路是：

a.建初始堆b.堆建好后，将堆顶输出，将最后一个节点交换至堆顶，调整堆，继续步骤b。

2)堆排序使用情况

a.快速找出n个值中的前k大或前k小的值

b.prim和kruskal算法使用到了堆

c.首先序列中有500个作业，按优先级建为堆，现在，我每次要处理优先级最高的，所以按堆操作依次取顶，并删除顶元素，可是在序列没处理完时又会加进来新作业，所以要用堆操作插入，以上操作是只有用堆才能实现的，直到某时间，确定不再会有新的作业插进来，便可由堆排序一次得到排序序列，这时，对排序的时间复杂度为恒定0（n\*log(n)),不会像其他排序那样有出入，而且空间复杂度为V(n),是最低的。

3)算法时间复杂度以及稳定性列表

![SouthEast][]

（注：稳定性是指排序之后两个数的前后关系不变)

[SouthEast]: /images/20220828/5f34d97f970240c5991e7137d5302d3e.png