- 一.冒泡排序(Bubble_Sort)
- 1.基本思想
- 2.过程：
- 3.平均时间复杂度
- 4.代码实现(c语言)
- 二.选择排序(select_sort)
- 1.基本思想
- 2.平均时间复杂度
- 3.代码实现(c语言)
- 三.插入排序(Insertion_Sort)
- 1.基本思想：
- 2.平均时间复杂度
- 3.代码(c语言)
- 四.希尔排序
- 1.基本思想
- 2.平均时间复杂度
- 3.代码实现(c语言)
- 五.归并排序(merge_sort)
- 1.基本思想
- 2.流程
- 3.时间复杂度
- 4.代码实现(c语言)
- *六.快速排序(quick_sort)
- 1.基本思想
- 2.时间复杂度
- 3.代码实现(c语言)
- 4.快速排序的优化
1.基本思想
- 两个数比较大小，较大的数下沉，较小的数冒起来。
- 比较相邻的两个数据，如果第二个数小，就交换位置。
- 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
- 继续重复上述过程，依次将第2 .3…n -1个最小数排好位置。
- O(n2)
#include二.选择排序(select_sort)int main() { int str[] = {2, 34, 5, 67, 888, 35, 7}; int len = sizeof(str) / sizeof(*str);//计算长度 for (int i = 0; i < n - 1; i++) //重复比较次数 { for (int j = 0; j < n - i - 1; j++) //元素比较次数 { if (str[j] > str[j + 1]) { int temp = str[j]; str[j] = str[j + 1]; str[j + 1] = temp;//交换 } } } for (i = 0; i < n; i++) { printf("%dn", str[i]); } return 0; }
1.基本思想
- 在长度为N的无序数组中，第一次遍历n - 1个数，找到最小的数值与第一个元素交换；
- 第二次遍历n - 2个数，找到最小的数值与第二个元素交换；
- 第n - 1次遍历，找到最小的数值与第n - 1个元素交换，排序完成。
- O(n2)
int main()
{
int str[] = {2, 34, 5, 67, 888, 35, 7};
int len= sizeof(str) / sizeof(*str);
for (int i = 0; i < len - 1; i++)
{
int min = i; // 记录最小值，第一个元素默认最小
for (int j = i + 1; j < len; j++) // 访问未排序的元素
{
if (str[j] < str[min]) // 找到目前最小值
{
min = j; // 记录最小值
}
}
if (min != i)
{
int temp = a[min]; // 交换两个变量
a[min] = a[i];
a[i] = temp;
}
}
return 0;
}
三.插入排序(Insertion_Sort)
1.基本思想：
- 开始把第一个数当作有序的，第二个向前找到合适的位置插入
- 在要排序的一组数中，假定前n - 1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。
- 如此反复循环，直到全部排好顺序。
- O(n2)
#include四.希尔排序int main() { int min, mark; int str[] = {2, 34, 5, 67, 888, 35, 7}; int n = sizeof(str) / sizeof(*str); for (i = 0; i < n - 1; i++) //进行次数 { mark = str[i + 1]; for (j = i + 1; mark < str[j - 1] && j > 0;j--) { str[j] = str[j - 1];//向前找，不满足条件则向后移动i+1个值被mark记录，因此可以被覆盖。 } str[j] = mark; //把mark放在正确位置 } for (i = 0; i < n; i++) { printf("%dn", str[i]); } return 0; }
1.基本思想
- 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
- 然后逐渐将增量减小, 并重复上述过程。直至增量为1, 此时数据序列有序
- O(n1.3)
#include五.归并排序(merge_sort)int main() { int j; int str[] = {2, 34, 5, 67, 888, 35, 7}; int len = sizeof(str) / sizeof(*str); //增量gap取的长度/2 for (int gap = len / 2; gap >= 1; gap = gap / 2) //几次增量，即由大到1的增量数列长度 { for (int i = 0; i < len / gap - 1; i++) //该增量下需要执行次数 { int temp = str[i + gap]; //记录待插入的值 for (j = i + gap; j >= gap && temp < str[j - gap]; j -= gap) //从增量的数列依次用插入排序 { str[j] = str[j - gap]; //大于待插入值向后移动 } str[j] = temp; //待插入值放入适合位置 } } for (int i = 0; i < len; i++) { printf("%dn", str[i]); } return 0; }
1.基本思想
- 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
- 首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
- 有序数列的合并
- 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
- 解决（Conquer）：用合并排序法对两个子序列递归的排序。
- 合并（Combine）：合并两个已排序的子序列已得到排序结果。
- o(nlogn)
- 典型空间换事件，基数过大时消耗过大内存
#include*六.快速排序(quick_sort)int C(int arr[], int start, int end) { if (start == end) { return 1; } //递归结束条件 int reg[end - start]; C(arr, start, (start + end) / 2); //递归直到只剩两个数 C(arr, (start + end) / 2 + 1, end); //同 int i = start; //第二段数列的开始 int j = (start + end) / 2 + 1; //第一段数列开始 int k = 0; while (i <= (start + end) / 2 && j <= end) { reg[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; } //将有序数列合并 while (i <= (start + end) / 2) { reg[k++] = arr[i++]; } while (j <= end) { reg[k++] = arr[j++]; } //存在两个有序数列不相等，因此将后续继续合并到reg j = 0; for (i = start; i <= end; i++) { arr[i] = reg[j++]; } //将其重新赋值到arr原位置 } int main() { int str[] = {2, 34, 5, 67, 888, 35, 7}; int len = sizeof(str) / sizeof(*str); C(str, 0, len - 1); for (int i = 0; i < len; i++) { printf("%dn", str[i]); } return 0; }
1.基本思想
- 先从数列中取出一个数作为key值，第一个数形成坑；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。 辅助理解：挖坑填数。
- 初始时 i = 0;j = 9; key = 72 由于已经将a[0] 中的数保存到key中，可以理解成在数组a[0] 上挖了个坑，可以将其它数据填充到这来。 从j开始向前找一个比key小的数。假如当j = 8，符合条件，填坑，形成新坑a[8]。
- 再找数字来填a[8] 这个坑。这次从i开始向后找一个大于key的数,假如当i = 3，符合条件，填坑，形成新坑。
- key = 72 再重复上面的步骤，先从后向前找，再从前向后找。但i j的值从上一次的位置向前进一 开始走。
- 从i开始向后找，假如当i = 5时，由于i == j退出。 此时，i = j = 5，而a [5] 刚好又是上次挖的坑，因此将key填入a[5]可以看出a[5] 前面的数字都小于它，a[5] 后面的数字都大于它。因此再对a[0…4] 和a[6…9] 这二个子区间重复上述步骤就可以了。
- O(nlogn)
- 最差O(n2)
//第一种方案
void quick(int arr[], int start, int end)
{
if (start >= end)
{
return;
}
int i = start, j = end, temp = arr[start]; //记录前面和最后的下表
while (i < j) //反复执行知道i==j
{
while (i < j && arr[j] > temp) //从右向左开始寻找一个数比基数小的数
{
j--;
} //找到则进行下一步
if (i < j)
{
arr[i++] = arr[j];
} //将坑填入形成新坑，i并将位置向前移动一个（因为下面步骤无需从i开始查找）
while (i < j && arr[i] < temp) //从左向右重复上述步骤
{
i++;
}
if (i < j)
{
arr[j--] = arr[i]; //同理j也无需从刚刚填入的新坑开始
}
}
arr[i] = temp; //i==j相等时说明一方形成新坑，另一方没有找到填入的数，刚好i为新坑填入基数值
quick(arr, start, j - 1); //分成两个数列重复操作；
quick(arr, j + 1, end); //分成两个数列重复操作；
}
//第二种方案
void quick(int arr[], int start, int end)
{
if (start >= end)
{
return;
}
int i = start, j = end, temp = arr[start]; //记录前面和最后的下表
while (i < j) //反复执行知道i==j
{
while (i < j && arr[j] > temp) //从右向左开始寻找一个数比基数小的数
{
j--;
} //找到则进行下一步
while (i < j && arr[i] < temp) //从左向右重复上述步骤
{
i++;
}
int temp = a[i];
a[i] = a[j];
a[j] = emp;//直接交换位置
}
arr[i] = temp;
quick(arr, start, j - 1); //分成两个数列重复操作；
quick(arr, j + 1, end); //分成两个数列重复操作；
}
//第三种方案，此方案仅供娱乐，效率贼低
void C(int arr[], int start, int end)
{
if (start >= end)
{
return;
}
int index = start + 1, j = start + 1, p1 = arr[start]; //index表示遍历位置，j表示index扫描到多少个数字比p1小
while (index <= end) //从左至右依次遍历
{
if (arr[index] < p1)
{
int temp = arr[index];
arr[index] = arr[j];
arr[j] = temp;
j++;
}//找到比p1小，放在j的位置，j++让下次扫描到的数字放在下一个位置
index++;
}
j--;
arr[start] = arr[j];
arr[j] = p1;//把p1和j前面那个满足条件的交换位置，也是前面j--的原因
C(arr, start, j - 1); //分成两个数列重复操作；
C(arr, j + 1, end); //分成两个数列重复操作；
}
4.快速排序的优化
- 将取两个基数，把数列分成三段
void C(int arr[], int start, int end)
{
int temp;
if (start >= end)
{
return;
} //结束条件
if (arr[start] > arr[end])
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
int index = start + 1, left = start + 1, right = end - 1; //index为扫描位置，从左向右left为当前需调换的数(即left前面的数都满足比p1小)，right同
int p1 = arr[start], p2 = arr[end]; //p1,p为两个基数
while (index <= right)
{
if (arr[index] < p1)
{
temp = arr[index];
arr[index] = arr[left];
arr[left] = temp; //比p1小与left调换
left++; //需要调换的数向前移动
}
else if (arr[index] >= p2) //必须等于p2，不然效率会变低
{
while (arr[right] > p2 && index < right)
{
right--;
} //判断该数是否需要调换（比p2大说明该数满足放在后面的条件，right前移）
temp = arr[right];
arr[right] = arr[index];
arr[index] = temp;
right--;
if (arr[index] < p1) //交换过后index可能出现比第一个基数小的情况，因此再次判断
{
temp = arr[index];
arr[index] = arr[left];
arr[left] = temp;
left++;
}
}
index++; //扫描位置向前移动
}
left--; //left（不包括left）前所有数满足比p1小，所以将left-1和start交换位置
right++;
arr[start] = arr[left];
arr[left] = p1;
arr[end] = arr[right];
arr[right] = p2;
C(arr, start, left - 1);
C(arr, left + 1, right - 1);
C(arr, right + 1, end); //分开递归
}
