C#快速排序-白红宇

1：需求

已知数组int[] max={72, 54, 59, 30, 31, 78, 2, 77, 82, 72};用快速排序算法按降序对其进行排列，并返回数组。

思路：

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。

2：代码

                
static
void
Main()
{ 
    
array = 
new
int
[] { 72, 54, 59, 30, 31, 78, 2, 77, 82, 72 };
    
QuickSort(0, array.Length - 1);
    
Console.WriteLine(
"The Result: "
);
    
for
(
int
i = 0; i < array.Length; i++)
    
{ 
        
Console.Write(array[i] + 
", "
);
    
}
    
Console.ReadKey();
}
private
static
int
[] array;
private
static
void
QuickSort(
int
lowest, 
int
highest)
{ 
    
if
(array == 
null
|| lowest < 0 || lowest >= highest
    
|| highest >= array.Length)
    
{ 
        
return
;
    
}
    
int
low = lowest;
    
int
high = highest;
    
int
key = low++;
    
for
(; low <= high; )
    
{ 
        
if
(key < high)
        
{ 
            
if
(array[key] > array[high])
            
{ 
                
array[high] = array[key] + (array[key] = array[high]) * 0;
                
key = high;
            
}
            
high--;
        
}
        
if
(key > low)
        
{ 
            
if
(array[key] < array[low])
            
{ 
                
array[low] = array[key] + (array[key] = array[low]) * 0;
                
key = low;
            
}
            
low++;
        
}
    
}
    
for
(
int
i = 0; i < array.Length; i++)
    
{ 
        
Console.Write(array[i] + 
", "
);
    
}
    
Console.WriteLine();
    
QuickSort(lowest, key - 1);
    
QuickSort(key + 1, highest);
}
        
      

3：时间复杂度

log2(n)*n

本文转自最课程陆敏技博客园博客，原文链接：http://www.cnblogs.com/luminji/archive/2012/07/18/2305613.html，如需转载请自行联系原作者