基础丢的差不多了,是时候该重新捡起来,不然真的心虚啊,于是就从排序开始,上 poj 找基础的排序题居然没有,悲催,太低级了,最后在 hdu 上找到一个排序题,http://acm.hdu.edu.cn/showprob…
忘得差不多也有一个好处,就是可以自己从头再想,这次决定不看任何参考资料,就凭着模糊的印象,慢慢的把算法的思路先理清楚,然后动手写,再手工调,一点点来,这样才能更好的理解,悲催的是,一个冒泡排就搞了一个上午啊
#include <stdio.h> #define MAX 1005 int get(int arr[]) { int n, i; scanf("%d", &n); for (i=0; i<n; i++) { scanf("%d", &arr[i]); } return n; } void print(int arr[], int n) { printf("%d", arr[0]); int i; for (i=1; i<n; i++) { printf(" %d", arr[i]); } printf("n"); } void sort(int arr[], int n) { int i, j; for (i=0; i<n-1; i++) { // printf("processing arr[%d]:%dn", i, arr[i]); for (j=0; j<n-i-1; j++) { // printf("checking for arr[%d]:%d and arr[%d]:%dn", // j, arr[j], j+1, arr[j+1]); if (arr[j] > arr[j+1]) { // printf("swapping arr[%d]:%d and arr[%d]:%dn", // j, arr[j], j+1, arr[j+1]); int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; // print(arr, n); } } } // printf("donen"); return; } int main() { int t; scanf("%d", &t); while (t--) { int arr[MAX] = {0}; int n = get(arr); sort(arr, n); print(arr, n); } return 0; }
遇到的问题在于,看高亮的第 32 行,如果把 for 循环的初始条件从 j=0 改成 j=i 就 WA 了,这是为什么呢,有兴趣的可以自己想想
冒泡排序出来了,选择也跟着很快就出来了
#include <stdio.h> #define MAX 1005 int get(int arr[]) { int n, i; scanf("%d", &n); for (i=0; i<n; i++) { scanf("%d", &arr[i]); } return n; } void print(int arr[], int n) { printf("%d", arr[0]); int i; for (i=1; i<n; i++) { printf(" %d", arr[i]); } printf("n"); } void sort(int arr[], int n) { int i, j; for (i=0; i<n-1; i++) { int min = i; for (j=i+1; j<n; j++) { if (arr[j] < arr[min]) { min = j; } } if (min != i) { int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } return; } int main() { int t; scanf("%d", &t); while (t--) { int arr[MAX] = {0}; int n = get(arr); sort(arr, n); print(arr, n); } return 0; }
选择排序是我觉得最自然,最好理解的排序方法,我记得当时大一的时候,刚接触 C ,什么都没学,自己琢磨出来的就是选择,倒是冒泡还费劲理解。。