비귀속 빠른 정렬과 비귀속 빠른 곱셈

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <stack>

 4 using namespace std;

 5 long long  re_pows(int a,int n)// 

 6 {

 7     if(n==0) return 1;

 8     long long t=re_pows(a,n/2);

 9     long long ans=t*t;

10     if(n&1) ans*=a;

11     return ans;

12 }

13 long long  ure_pows(int a,int n)// 

14 {

15     int i=1;

16     while(i<=n)i<<=1;

17     long long ans=1;

18     while(i>>=1)

19     {

20         ans*=ans;

21         if(n&i) ans*=a;

22     }

23     return ans;

24 }

25 int arr[100]={1,2,4,5,3};

26 struct node

27 {

28     int l,r;

29     node(){}

30     node(int a,int b){l=a;r=b;}

31 };

32 int part(int l,int r)

33 {

34     int i=l-1,j=l;

35     while(j<r)

36     {

37         if(arr[j]<arr[r])

38             swap(arr[++i],arr[j++]);

39         else j++;

40     }

41     swap(arr[++i],arr[r]);

42     return i;

43 }

44 

45 void re_qsort(int l,int r)// 

46 {

47     if(l>=r) return;

48     int m=part(l,r);

49     re_qsort(l,m-1);

50     re_qsort(m+1,r);

51 }

52 

53 stack<node> q;

54 void ure_qsort(int l,int r)// 

55 {

56     q.push(node(l,r));

57     while(!q.empty())

58     {

59         l=q.top().l;

60         r=q.top().r;

61         q.pop();

62         while(l<r)

63         {

64             int m=part(l,r);

65             q.push(node(m+1,r));// 

66             r=m-1;

67         }

68     }

69 }

70 int main()

71 {

72     int i,n;

73     while(cin>>n)

74     {

75         for(i=0;i<n;i++)

76         {

77             cin>>arr[i];

78         }

79         ure_qsort(0,n-1);

80         for(i=0;i<n;i++)

81         {

82             cout<<arr[i]<<' ';

83         }

84         cout<<endl;

85     }

86     return 0;

87 }