當前位置:網站首頁>快速排序模板整理,實戰培訓

快速排序模板整理,實戰培訓

2021-08-20 04:05:27 程序員小李子

並將排好序的數列按順序輸出。

輸入格式

輸入共兩行,第一行包含整數 n。

第二行包含 n 個整數(所有整數均在1~109範圍內),錶示整個數列。

輸出格式

輸出共一行,包含 n 個整數,錶示排好序的數列。

數據範圍

1≤n≤100000

輸入樣例:

5

3 1 2 4 5

輸出樣例:

1 2 3 4 5

代碼:


//快速排序模板

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 1e5 + 10;

int q[maxn];

void quick_sort(int q[],int l,int r)

{

	if (l >= r)  return;

	int i = l - 1, j = r + 1, x = q[l + r >> 1];

	while (i < j)

	{

		do i++; while (q[i] < x);

		do j--; while (q[j] > x);

		if (i < j) swap(q[i], q[j]);

	}

	quick_sort(q, l, j), quick_sort(q, j + 1, r); 

}

int main()

{

	int n;

	cin >> n;

	for (int i = 1; i <= n; i++)

	{

		cin >> q[i];

	}

	quick_sort(q, 1, n);

	for (int i = 1; i <= n; i++)

	{

		cout << q[i] << " ";

	}

	cout << endl;

	return 0;

} 


     
  • 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.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.

第k個數

給定一個長度為n的整數數列,以及一個整數k,請用快速選擇算法求出數列的第k小的數是多少。

輸入格式

第一行包含兩個整數 n 和 k。

第二行包含 n 個整數(所有整數均在1~109範圍內),錶示整數數列。

輸出格式

輸出一個整數,錶示數列的第k小數。

數據範圍

1≤n≤100000,

1≤k≤n

輸入樣例:

5 3

2 4 1 5 3

輸出樣例:

3


#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 1e5 + 10;

int q[maxn];

int n, k;

int quick_sort(int q[],int l, int r, int k)



# **感受:**

其實我投簡曆的時候,都不太敢投遞阿裏。因為在阿裏一面前已經過了字節的三次面試,投阿裏的簡曆一直沒被撈,所以以為簡曆就掛了。

特別感謝一面的面試官撈了我,給了我機會,同時也認可我的努力和態度。對比我的面經和其他大佬的面經,自己真的是運氣好。別人8成實力,我可能8成運氣。所以對我而言,我要繼續加倍努力,彌補自己技術上的不足,以及與科班大佬們基礎上的差距。希望自己能繼續保持學習的熱情,繼續努力走下去。

**也祝願各比特同學,都能找到自己心動的offer。**

分享我在這次面試前所做的准備(刷題複習資料以及一些大佬們的學習筆記和學習路線),都已經整理成了電子文檔,**[需要的朋友可以【點贊+關注】戳這裏即可免費獲取](https://gitee.com/vip204888/java-p7)**

![拿到字節跳動offer後,簡曆被阿裏撈了起來,二面迎來了P9"盤問"](https://s2.51cto.com/images/20210820/1629402515819843.jpg)
     
  • 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.

版權聲明
本文為[程序員小李子]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2021/08/20210820040527455p.html

隨機推薦