9 solutions

  • 1
    @ 2022-4-3 17:58:35

    这题,我觉得 放在这里 是想 让大家 手写 一下 一些 排序算法的。要不然 放在这里的 意义 真没多大。手写 排序 其实 真的 挺重要的,我听一个 大佬说过,有时候 要自己 写排序的。而且 排序的思想 很基础。

    #include <iostream>
    
    using namespace std;
    
    int arr1[500005];
    
    void quickSort(int l, int r) {
    	if (l >= r) {
    		return;
    	}
    	//int ic = arr1[r];
    	int midIndex = arr1[r];
    	int s = l;
    	int e = r - 1;
    	while (true) {
    		while (s < r && arr1[s] < midIndex) {
    			s++;
    		}
    		while (e >= l && arr1[e] > midIndex) {
    			e--;
    		}
    		if (s < e) {
    			int temp = arr1[s];
    			arr1[s] = arr1[e];
    			arr1[e] = temp;
    
    			// 继续 往下搜
    			s++;
    			e--;
    		}
    		else {
    			break;
    		}
    	}
    	int temp = arr1[s];
    	arr1[s] = arr1[r];
    	arr1[r] = temp;
    	quickSort(l,s -  1);
    	quickSort(s + 1, r);
    }
    
    
    
    int main(void) {
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; ++i) {
    		cin >> arr1[i];
    	}
    
    	quickSort(0, n - 1);
    
    	for (int i = 0; i < n; ++i) {
    		cout << arr1[i] << " ";
    	}
    
    	return 0;
    }
    

    Information

    ID
    109
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    339
    Accepted
    85
    Uploaded By