基础练习-数列排序

Myth丶恋晨 2022-01-14 16:07 232阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

# **问题描述** #

给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200

# **输入格式** #

第一行为一个整数n。  
　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。

# **输出格式** #

输出一行，按从小到大的顺序输出排序后的数列。

# **样例输入** #

>         5  
>         8 3 6 4 9

# **样例输出** #

>         3 4 6 8 9

# **思路** #

1.  使用数组接收输入的待排序数据
2.  使用快速排序算法进行排序

# **代码实现** #

#include <stdio.h>
    
    void swap(int *num, int low, int high);
    int partition (int *num, int low, int high);
    void quickSort(int *num, int low, int high);
    int main (void) {
    	int time, i;
    	scanf("%d", &time);
    	int number[time + 1];
    	for (i = 1; i <= time; i++) {
    		scanf("%d", &number[i]);
    	}
    	quickSort(number, 1, time);
    	for (i = 1; i <= time; i++) {
    		printf("%d\t", number[i]);
    	}
    	return 0;
    }
    
    void swap(int *num, int low, int high) {
    	int middle = 0;
    	middle = num[low];
    	num[low] = num[high];
    	num[high] = middle;
    }
    /**
     * 快速排序实现
     */
    int partition (int *num, int low, int high) {
    	int provke = num[low];
    	while (low < high) {
    		while (low < high && num[high] > provke) {
    			high--;
    		}
    		swap(num, low, high);
    		while(low < high && num[low] <= provke) {
    			low++;
    		}
    		swap(num, low, high);
    	}
    }
    
    void quickSort(int *num, int low, int high) {
    	int provke;
    	if(low < high) {
    		provke = partition(num, low, high); 
    		quickSort(num, low, provke - 1);
    		quickSort(num, provke + 1, high);
    	}
    }

转载于:https://my.oschina.net/niithub/blog/3017252

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/ff3bd4f4e35e40fd84bb31688d572966.png