/
Program.cs
89 lines (79 loc) · 2.03 KB
/
Program.cs
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QuickSortExample
{
class Program
{
static void Main(string[] args)
{
int[] a = { 3, 2, 5, 6,7,8,9,10 };
QuickSortHoar qsh = new QuickSortHoar();
qsh.Execute(ref a,0,a.Length-1);
foreach (var val in a) Console.Write(val+" ");
Console.Read();
}
}
class QuickSortHoar
{
void Swap(ref int i,ref int j)
{
int temp = i;
i = j;
j = temp;
}
public void Execute(ref int[] a, int lo, int hi)
{
int p = a[(hi - lo) / 2 + lo];
int i = lo, j = hi;
while (i <= j)
{
while (a[i] < p && i <= hi) ++i;
while (a[j] > p && j >= lo) --j;
if (i <= j)
{
Swap(ref a[i],ref a[j]);
++i; --j;
}
}
if (j > lo) Execute(ref a, lo, j);
if (i < hi) Execute(ref a, i, hi);
}
}
}
//
/*
* int partition(ref int[] a,int lo,int hi)
{
int pivot = a[lo];
int i = lo-1;
int j = hi+1;
while (i<=j)
{
// while (a[++i] <= pivot) { if (i == hi) break; } //do { i++; }
// while (a[--j] >= pivot) { if (j == lo) break; } //do { j--; }
while (a[++i] < pivot && i <= hi) { if (i == hi) break; }
while (a[--j] > pivot && j >= lo) { if (j == lo) break; }
if (i <= j)
{
swap(ref a[i], ref a[j]);
++i;++j;
return j;
}
}
return j;
}
public void Execute(ref int[] a, int lo, int hi)
{
if (lo < hi)
{
int p = partition(ref a,lo,hi);
Execute(ref a,lo,p);
Execute(ref a, p, hi);
}
}
*
*
*/