冒泡排序

冒泡排序相对来说思路简单,思想如下(升序):
遍历数组,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧元素时,位置不变。这样第一轮排序的最后最大的元素就到了队尾,接下来进行第二轮排序,直到数组有序。
冒泡排序是一种稳定排序,平均时间复杂度是 **O(n²)**。

冒泡排序代码

代码

public static int[] Bubble(int[] s)
{
int len = s.Length;
for (int i = len; i > 0; --i)
{
for (int j = 0; j < len-1; ++j)
{
if (s[j] > s[j + 1])
{
int temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
}
}
}
return s;
}
 

快速排序

快速排序的思路是:每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成两个部分。
这种思路叫做分治法。
平均时间复杂度为 O(nlogn)**,最坏情况下为O(n²)**。

几种实现方法(升序)

双边循环法
设置基准元素pivot,设置left和right左右指针,每一次循环分别找到左边比基准元素大,右边比基准元素小的两个index,然后交换这两个元素,直到 left==right。

代码

双边循环代码
public static void QuickSort(int[] s,int startIndex,int endIndex)
{
//递归结束条件
if (startIndex >= endIndex)
return;
//得到基准元素位置
int pivotIndex = Partition(s, startIndex, endIndex);
//根据基准元素,分成两部分进行递归排序
QuickSort(s, startIndex, pivotIndex-1);
QuickSort(s, pivotIndex + 1, endIndex);
}
static int Partition(int[] s,int startIndex,int endIndex)
{
//取第一个位置元素为基准元素
int pivot = s[startIndex];
int left = startIndex;
int right = endIndex;

while(left!=right)
{
//控制right指针比较并左移
while (left < right && s[right] > pivot)
{
right--;
}
//控制left指针比较并右移
while (left < right && s[left] <= pivot)
{
left++;
}
//交换left和right指针所指向的元素
if(left<right)
{
int p = s[left];
s[left] = s[right];
s[right] = p;
}
}

//pivot和指针重合点交换
s[startIndex] = s[left];
s[left] = pivot;

return left;
}
 

单边循环
设置基准元素pivot,设置一个mark指针,指向数列起始位置。

接下来,从基准元素的下一个位置开始遍历数组。

如果遍历到的元素大于基准元素,就继续往后遍历。

如果遍历到的元素小于基准元素,则需要做两件事:第一,把mark指针右移1位,因为小于pivot
的区域边界增大了1;第二,让最新遍历到的元素和mark指针所在位置的元素交换位置,因为最
新遍历的元素归属于小于pivot的区域。

代码(仅改变了Partition中的代码)

单边循环代码
static int Partition(int[] s,int startIndex,int endIndex)
{
int pivot = s[startIndex];
int mark = startIndex;

for (int i = startIndex + 1; i <= endIndex; i++)
{
if(s[i]<pivot)
{
mark++;
if(mark!=i)
{
int p = s[i];
s[i] = s[mark];
s[mark] = p;
}
}
}

s[startIndex] = s[mark];
s[mark] = pivot;

return mark;
}
 

非递归实现
绝大多数的递归逻辑,都可以用栈的方式来代替。

堆排序

堆排序建立在二叉堆的基础上,思路:

  1. 把无序数组构建成二叉堆。需要从小到大排序,则构建成最大堆;需要从大到小排序,则构建成最小堆。
  2. 循环删除堆顶元素,替换到二叉堆的末尾,调整堆产生新的堆顶。

代码

堆排序代码
static void downAdjust(int[] array,int parentIndex,int length)
{
//temp 保存父节点值,用于最后赋值
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;

while(childIndex<length)
{
//如果有右孩子,且右孩子大于左孩子的值,则定位到右孩子
if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex])
childIndex++;

//如果父节点大于任何一个孩子的值,则直接跳出
if (temp >= array[childIndex])
break;

//无须真正交换,单项赋值即可
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = childIndex * 2 + 1;
}
array[parentIndex] = temp;
}

public static void HeapSort(int[] array)
{
int len = array.Length;

//将无序数组构建成最大堆
for (int i = (len - 2) / 2; i >= 0; i--)
{
downAdjust(array, i, len); //从最后一个非叶子节点开始进行“下沉”操作
}

for (int i = len - 1; i > 0; i--)
{
//最后一个元素和第一个元素进行交换
int temp = array[i];
array[i] = array[0];
array[0] = temp;

//“下沉”调整最大堆
downAdjust(array, 0, i);
}
}

计数排序

适用于一定范围内的整数排序,思路:
根据整数取值范围确定数组,遍历整数序列,将每一个整数按照其值对号入座,同时,对应数组下标的元素进行加1操作。最后直接输出这个数组,直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次。

数组大小的确定:len = 数列最大值-最小值+1

变形:从统计数组的第二个元素开始,每一个元素都加上前面所有元素之和(可以用于确定相同整数的排序,如成绩排名)

计数排序代码
public static int[] CountSort(int[] array)
{
//得到数列的最大值和最小值,并计算差值d
int max = array[0];
int min = array[0];

for(int i=0;i<array.Length;i++)
{
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}

int d = max - min;

//创建统计数组并统计对应元素个数
int[] countArray = new int[d + 1];
for(int i=0;i<array.Length;i++)
{
countArray[array[i] - min]++;
}

//统计数组做变形,后面的元素等于前面的元素之和
for(int i=1;i<countArray.Length;i++)
{
countArray[i] += countArray[i - 1];
}

//倒序遍历原始数列,从统计数组找到正确位置,输出到结果数组
int[] sortedArray = new int[array.Length];
for(int i=array.Length-1;i>=0;i--)
{
sortedArray[countArray[array[i] - min] - 1] = array[i];
countArray[array[i] - min]--;
}
return sortedArray;
}
 

桶排序

线性时间的排序算法。
每一个桶(bucket)代表一个区间范围,里面可以承载一个或多个元素。

具体需要建立多少个桶,如何确定桶的区间范围,有很多种不同的方式。我们这里创建的桶数量
等于原始数列的元素数量,除最后一个桶只包含数列最大值外,前面各个桶的区间按照比例来确
定。
思路:

  1. 确定桶的区间范围

区间跨度 = (最大值-最小值) / (桶的数量-1)
2. 遍历原始数列,把元素对号入座放入各个桶中。
3. 对每个桶内部的元素分别进行排序。
4. 遍历所有的桶,输出所有元素。

常用排序算法复杂度

图片