快速排序c++/c实现

在lintcode刷题目的时候,遇到了下面的题目

在数组中找到第k大的元素

给出数组 [9,3,2,4,8]，第三大的元素是 4

给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

于是乎,复习了一下快速排序.

//快速排序的代码实现
// 12,56,72,1,5, 35,74,44,63,52
// 1 5 12 35 44   52 56 63 72 74

//使用快排的思路
// 12 56 72 1 5 35 74 44 63 52
// 设置两个标志 i和j,分别指向数组的开始和结束. i = 0 , j = 9;
//   首先是去排12的位置 , 从右侧开始 ,找小的
// 12 > 1 交换且左侧标记i++
//   5 56 72 1 12 35 74 44 63 52
// 从左侧开始,找大的,56 > 12 ,则交换位置,且j--
// 5 12 72 1 56 35 74 44 63 52
// 从右侧找小的 , 1 <１２　，交换两个位置，且ｉ＋＋
// 5 1 72 12 56 35 74 44 63 52
// 从左侧找大的, 72 > 12 ,交换位置,j--;
// 5 1 12 72 56 35 74 44 63 52
// 当前i = 3 ,j = 3 ,第一趟排序完成.
// 12 被排到了 2的位置上, 之后对0 - 1和 3 - 9递归调用快排

  1 #include <iostream>
  2 #include <unistd.h>
  3 using namespace std;
  4 
  5 
  6 
  7 void quicksort(int a[],int s,int e);
  8 int SearchByQuickSort(int a[],int s,int e,int k);
  9 
 10 int main()
 11 {
 12     int arr[10] = {12,56,72,1,5, 35,74,44,63,52};
 13     quicksort(arr,0,9);
 14     for(int i = 0;i<10;i++)
 15     {
 16         cout << arr[i] << "	" ;
 17     }
 18     cout <<endl;
 19     for(int i=0;i<10;i++)
 20     {
 21         int tmp5 = SearchByQuickSort(arr,0,9,i);
 22         cout << tmp5 <<"	";
 23     }
 24     cout <<endl;
 25 }
 26 
 27 void quicksort(int a[],int s,int e)
 28 {
 29     //递归的返回
 30     if(s == e)
 31     {
 32         return ;
 33     }
 34     int i,j;
 35     int port = 0;   //1表示左端 0表示右端
 36     int key = a[s];
 37     int NumKey = s;
 38     for(i = s,j = e;i != j;){
 39         if(port == 0){
 40             if(a[j] < key){
 41                 cout << a[j] << " << " << key <<endl;
 42                  a[NumKey] = a[j];
 43                  NumKey = j;
 44                  port = 1;
 45                  i++;
 46             }
 47             else{
 48                 j--;
 49             }
 50         }
 51         else{
 52             if(a[i] > key){
 53                 cout << a[i] << " << " << key <<endl;
 54                  a[NumKey] = a[i];
 55                  NumKey = i;
 56                  port = 0;
 57                  j--;
 58             }
 59             else{
 60                 i++;
 61             }
 62         }
 63     }
 64     a[NumKey] = key;
 65     //通过递归排序去排剩下的.
 66     
 67     if(NumKey == s)
 68     {
 69         quicksort(a,NumKey+1,e);
 70     }
 71     else if(NumKey == e)
 72     {
 73         quicksort(a,s,NumKey-1);
 74     }
 75     else
 76     {
 77         quicksort(a,NumKey+1,e);
 78         quicksort(a,s,NumKey-1);
 79     }    
 80 }
 81 
 82 int SearchByQuickSort(int a[],int s,int e,int k)
 83 {
 84     //递归的返回
 85     if(s == e)
 86     {
 87         if(k == e)
 88         {
 89             return a[e];
 90         }
 91         else
 92         {
 93             return 0;
 94         }
 95     }
 96     int i,j;
 97     int port = 0;   //1表示左端 0表示右端
 98     int key = a[s];
 99     int NumKey = s;
100     for(i = s,j = e;i != j;){
101         if(port == 0){
102             if(a[j] < key){
103                 cout << a[j] << " << " << key <<endl;
104                  a[NumKey] = a[j];
105                  NumKey = j;
106                  port = 1;
107                  i++;
108             }
109             else{
110                 j--;
111             }
112         }
113         else{
114             if(a[i] > key){
115                 cout << a[i] << " << " << key <<endl;
116                  a[NumKey] = a[i];
117                  NumKey = i;
118                  port = 0;
119                  j--;
120             }
121             else{
122                 i++;
123             }
124         }
125     }
126     a[NumKey] = key;
127     if(NumKey == k)
128     {
129         return a[NumKey];
130     }
131     //通过递归排序去排剩下的.
132     
133     int x = 0;
134     if(NumKey == s)
135     {
136         x = SearchByQuickSort(a,NumKey+1,e,k);
137     }
138     else if(NumKey == e)
139     {
140         x = SearchByQuickSort(a,s,NumKey-1, k);
141     }
142     else
143     {
144         x = SearchByQuickSort(a,NumKey+1,e,k);
145         x += SearchByQuickSort(a,s,NumKey-1,k);
146     }
147     return x;    
148 }