-
Notifications
You must be signed in to change notification settings - Fork 0
/
0912-Sort-an-array.cs
91 lines (72 loc) · 2.06 KB
/
0912-Sort-an-array.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
90
91
using System;
using System.Collections.Generic;
using System.Text;
namespace Solution._0912.Sort_an_array
{
public class _0912_Sort_an_array
{
public int[] SortArray(int[] nums)
{
//Array.Sort(nums);
//return nums;
QuickSort(ref nums, 0, nums.Length - 1);
return nums;
}
private void QuickSort(ref int[] data, int left, int right)
{
if (left >= right)
return;
int i = Partition(data, left, right);
QuickSort(ref data, left, i - 1);
QuickSort(ref data, i + 1, right);
}
private int Partition(int[] data, int left, int right)
{
int i = left;
int pivot = data[right];
for (int j = left; j < right; j++)
{
if (data[j] < pivot)
{
Swap(ref data, i, j);
i++;
}
}
Swap(ref data, i, right);
return i;
}
private void Swap(ref int[] nums, int i, int j)
{
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
//public int[] QuickSort(int[] data, int left, int right)
//{
// if (left >= right)
// return data;
// int pivot = data[left];
// int i = left;
// int j = right;
// int tmp;
// while (i != j)
// {
// while (data[j] >= pivot && i < j)
// j--;
// while (data[i] <= pivot && i < j)
// i++;
// if (i < j)
// {
// tmp = data[j];
// data[j] = data[i];
// data[i] = tmp;
// }
// }
// data[left] = data[i];
// data[i] = pivot;
// QuickSort(data, left, i - 1);
// QuickSort(data, i + 1, right);
// return data;
//}
}
}