一、冒泡排序
1、算法思想
冒泡排序是一种简单的排序算法，通过循环遍历，将临近的两个元素进行比较，满足排序规则时，进行下一组元素对比，当不满足排序规则时，将两个元素交换位置，再继续进行下一组元素对比，确保最大的元素在一遍循环过后一定排在最后面，然后最后通过最多n2次循环对比，直到完全有序。
2、算法描述
冒泡过程.gif
（1）比较两个相邻的元素，如果第一个比第二个大，那么就交换他们的位置。
（2）重复步骤（1）的操作，依次比较两两相邻的两个元素。所有元素对比过后表示一次循环结束。
（3）至多循环n-1次，重复上面两个步骤。
（4）直到没有任何一组元素需要交换位置表示排序完成。
3、代码实现
void BubbleSort(int* slist,int length)
{
int temp;
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - 1 - i; j++)
{
if (slist[j] > slist[j + 1])
{
temp = slist[j];
slist[j] = slist[j + 1];
slist[j + 1] = temp;
}
}
}
}
int main()
{
int sortlist[] = { 5,0,4,1,8,3,7 };
BubbleSort(sortlist,7);
}
4、算法复杂度
最好的情况为正序，只需要一遍遍历，所以时间复杂度为O(n),最坏的情况为逆序，需要遍历n2次，所以时间复杂度为O(n2)。由于只有一个交换的变量temp需要内存，所以空间复杂度为O(1)。
二、插入排序
1、算法思想
将列表中的每个元素依次和之前排好序的元素进行比较，找到合适的位置插入，使之前有序的列表保持依然有序。
2、算法描述
插入排序.gif
（1）从第2个元素开始，选取第2个元素（i），认为第1个元素为一个只有一个元素的有序列表。
（2）将选取的元素与之前的元素依次比较，如果选取的元素小于于列表中的元素，交换他们的位置。
（3）选取下一个元素（i+1），重复步骤（2），直至列表中的每个元素都进行了步骤（2）的操作。
3、代码实现
//方法一
void InsertSort1(int* slist,int length)
{
int temp;
for (int i = 1; i < length; i++)
{
int j = i -1;
while (slist[j] > slist[j+1] && j >= 0)
{
//交换位置
temp = slist[j];
slist[j] = slist[j+1];
slist[j+1] = temp;
j--;
/*或者这样交换*/
// slist[j+1] = slist[j] + slist[j+1];
// slist[j] = slist[j+1] - slist[j];
// slist[j+1] = slist[j+1] - slist[j];
// j--;
}
}
}
//方法二
void InsertSort2(int* slist,int length)
{
for (int i = 1; i < length; i++)
{
int j = i - 1;
int number = slist[i];
while (j >= 0 && slist[j] > number)
{
slist[j+1] = slist[j];
j--;
}
slist[j+1] = number;
}
}
4、算法复杂度
最好的情况为正序，只需要一遍遍历，所以时间复杂度为O(n),最坏的情况为逆序，需要遍历n2次，所以时间复杂度为O(n2)。空间复杂度为O(1)。
三、选择排序
1、算法思想
从头开始，遍历列表找到最小值，把最小的值放在第一个位置，在遍历找到第二小的值放在第一个后面，以此类推，知道最后一个排好序。
2、算法描述
选择排序.jpg
（1）遍历整个列表N个元素，找到最小的元素，与第一个元素交换位置。
（2）遍历剩余的N-1个元素，找到最小的元素，将它排在剩余N-1个元素的第一个。
（3）以此类推，重复步骤（2），直到N-1小于1。
3、代码实现
void SelectSort(int* slist, int length)
{
int min;
int temp;
for (int i = 0; i < length; i++)
{
min = i;
for (int j = i + 1; j < length; j++)
{
if (slist[j] < slist[min])
{
min = j;
}
}
temp = slist[i];
slist[i] = slist[min];
slist[min] = temp;
}
}
4、算法复杂度
不管最后还是最坏的情况，选择排序的时间复杂度都是O(n2)，空间复杂度为O(1)。
四、归并排序
1、算法思想
归并排序采用分治的思想，将一个列表分为多个子列表，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
2、算法描述
归并排序.png
（1）将列表元素对半分开，分为两个列表。
（2）重复步骤（1），直至每个列表只有一个元素。
（3）将两个相邻的列表排序，直至真个列表有序。
3、代码实现
//排序
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
{
//i:第一个待排序的起始位置，
int i = startIndex;
//j:第二个待排序的起始位置，
int j = midIndex + 1;
int k = startIndex;
while (i != midIndex + 1 && j != endIndex+1)
{
if (sourceArr[i] > sourceArr[j])
{
tempArr[k] = sourceArr[j];
k++;
j++;
}
else
{
tempArr[k] = sourceArr[i];
k++;
i++;
}
}
//将两个中未排序的添加到tempArr中
while (i != midIndex + 1)
{
tempArr[k] = sourceArr[i];
i++;
k++;
}
//将两个中未排序的添加到tempArr中
while (j != endIndex+1)
{
tempArr[k] = sourceArr[j];
j++;
k++;
}
//将tempArr中的元素赋值给sourceArr
for (int i = startIndex; i <= endIndex; i++)
{
sourceArr[i] = tempArr[i];
}
}
//分解递归
void BranchSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
if (startIndex < endIndex)
{
int mid = startIndex + (endIndex - startIndex) / 2;
BranchSort(sourceArr, tempArr, startIndex, mid);
BranchSort(sourceArr, tempArr, mid+1, endIndex);
MergeSort(sourceArr, tempArr, startIndex, mid, endIndex);
}
}
4、算法复杂度
归并排序是稳定排序算法，假设数组长度为n，那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。
五、希尔排序
1、算法思想
希尔排序，也称递减增量排序算法。将整个列表根据增量分为若干个子列表分别进行插入排序。随着增量的减小，列表趋于基本有序，当增量为1时，相当再做一次插入排序，使列表有序。
2、算法描述
希尔排序.png
（1）选择一个增量gap，一般为列表长度的一半。
（2）将列表中元素下标每隔gap的元素组成一个新的子列表。
（3）对每个子列表进行插入排序。
（4）将gap去原来的一半，重复步骤（2）（3），直到gap小于1。
3、代码实现
void ShellSort(int* slist, int length)
{
int temp;
//gap为增量，一般取长度的一般
int gap = length / 2;
//当增量小于1时结束排序
while (gap >= 1)
{
//最多分为gap个列表
for (int i = 0; i < gap; i++)
{
//下面的代码为一个简单的插入排序，只是插入排序的数组下标每次移动的不是1而是gap
for (int j = i+gap; j < length; j = j + gap)
{
if (slist[j] < slist[j-gap])
{
int k = j - gap;
int temp = slist[j];
while (k >= 0 && slist[k] > temp)
{
slist[k + gap] = slist[k];
k = k - gap;
}
slist[k+gap] = temp;
}
}
}
//增量递减
gap = gap/ 2;
}
}
4、算法复杂度
希尔排序是不稳定的排序，它时间复杂度和步长的选择有关。
看如下两个增量序列：
n/2、n/4、n/8...1
1、3、7...2^k-1
第一个序列称为希尔增量序列，使用希尔增量时，希尔排序在最坏情况下的时间复杂度为O(n2)。
第二个序列称为Hibbard增量序列，使用Hibbard增量时，希尔排序在最坏情况下的时间复杂度为O(n3/2)。
六、快速排序
1、算法思想
快速排序采用分治的思想，通通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数据变成有序序列。
2、算法描述
快速排序.jpg
（1）选定一个基准元素
（2）从右往左找到比基准元素小的元素
（3）从左往右找到比基准元素大的元素
（4）交换左右找到的两个元素的位置
（5）重复上面（2）（3）（4）步，直至左右两个元素相遇。
3、代码实现
void QuickSort(int* slist, int left, int right)
{
if (left >= right)
{
return;
}
int i = left;
int j = right;
int key = slist[left];
int temp;
//直到遍历完整个列表
while (i < j)
{
//从右到左找到小于key的下标
while (i<j&&slist[j] >= key)
{
j--;
}
//从左到右找到大于key的下标
while (i<j && slist[i] <= key)
{
i++;
}
//交换找到的两个元素,保证小的元素在前，大的元素在后
if (i < j)
{
temp = slist[i];
slist[i] = slist[j];
slist[j] = temp;
}
}
//将key元素交换到中间，确保分为大小两个列表
temp = slist[left];
slist[left] = slist[j];
slist[j] = temp;
QuickSort(slist, left, j - 1);
QuickSort(slist, j + 1, right);
}
void QuickSort2(int* slist, int left, int right)
{
if (left >= right)
{
return;
}
int j = left-1;
int key = slist[right];
int temp;
for (int i = left; i < right; i++)
{
//遍历整个列表，找到小于key的元素个数，并且通过交换位置，让他们的下标都在j的前面
if (slist[i] < key)
{
j++;
if (i != j)
{
temp = slist[i];
slist[i] = slist[j];
slist[j] = temp;
}
}
}
//将key的位置与j+1的位置互换，保证将slist列表分为小于slist[j+1]与大于slist[j+1]的两个列表
slist[right] = slist[j + 1];
slist[j + 1] = key;
QuickSort2(slist,left,j);
QuickSort2(slist, j+2, right);
}
4、算法复杂度
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。
网友评论