阅读量:1
排序
排序分为
1.插入排序([直接插入排序、希尔排序)
2.选择排序(直接选择排序、堆排序)
3.交换排序(冒泡排序、快速排序)
4.归并排序
插入排序
一趟插入排序：
在一串有序数字中插入数字tmp，先将tmp和最后一个数字比较，如果比它大，就将tmp放在它的后面；如果比它小，就将它往后挪动一位，将tmp和前一个数字继续比较。重复上述过程，直到tmp比某个数字大就放到该数字的后面，如果没有比tmp大的数字，就将tmp放在最前面。
void InsertSort(int a[], int n) { for (int i = 1; i < n; i++) { //假设[0, end]有序，则插入tmp后依然有序 int end = i - 1; int tmp = a[i]; while (end >= 0) { if (tmp < a[end]) { //挪动数据 a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } }希尔排序
希尔排序实际上是插入排序的加强版，相比于插入排序，希尔排序多了几趟预排序，而且这几趟预排其实也是插入排序的思想。
一趟预排序，就是先将数据分成gap组（每一组数与数的间隔为gap），每组再进行插入排序。每一趟预备排序完成后，将gap的值缩小，进行下一趟预排，直到最后gap变成1，接下来就完全变成了上面的插入排序。
gap =gap一半
void ShellSort(int a[], int n) { while (gap > 1) { //一趟预排序 int gap = gap / 3 + 1; //gap组数据排序 for (int i = 0; i < gap; i++) { //一组数据排序 for (int j = gap + i; j < n; j += gap) { int end = j - gap; int tmp = a[j]; while (end >= 0) { if (tmp < a[end]) { //挪数据 a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } }这个是两重循环
void ShellSort(int a[], int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = gap; i < n; i++) { int end = i - gap; int tmp = a[i]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }前者的每一趟排序是先排完一组，再排下一组 ，而后者是多组并排。因为组与组之间是互不影响的，不一定非要排完一组再进行下一组。虽然说少了一层循环，但时间复杂度是不变的，所以两种写法都是可以的，根据自己的口味选择。
平均时间复杂度：T(n) = O(n^1.5) 最坏时间复杂度：T(n) = O(nlog²n） 空间复杂度: O(1) 稳定性: 不稳定，由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
希尔排序的优点是它对大规模数据的排序非常有效，尤其是当数据已经部分有序时。希尔排序通过将数组分为多个子序列来减少比较的次数，然后逐步缩小子序列的间隔，直到最后进行一次完整的直接插入排序。这种方法使得希尔排序在处理大规模数据时比传统的直接插入排序快得多。
选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
用人话说，选择排序就像是在玩一个游戏，你需要找到数组中的最小值，然后将其“提拔”到数组的第一个位置。然后，你需要找到数组中的下一个最小值，并将其“提拔”到数组的第二个位置。你继续这个过程，直到数组中的所有元素都被“提拔”到它们正确的位置。
思路 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： 1.初始状态：无序区为R[1…n]，有序区为空； 2.第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区； 3.n-1趟结束，数组有序化了。
void SelectSort(int a[], int n) { for (int i = 0; i < n; i++) { int mini = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[mini]) { mini = j; } } Swap(&a[mini], &a[i]); } }上面的过程是从前往后排，每一趟只能排一个数。其实可以优化一下，从两头向中间靠拢，每一趟选出一个最大值和最小值放在两边，当两边相遇时排序就完成了。
void SelectSort(int a[], int n) { int begin = 0; int end = n - 1; while (begin < end) { int mini = begin; int maxi = end; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //交换 Swap(&a[begin], &a[mini]); //如果maxi和begin重叠则maxi需要修正，因为begin的位置已经不是原来的值了 if (maxi == begin) { maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; } }堆排序
堆排序是一种基于比较的排序算法，它利用了堆这种数据结构。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
用人话说，堆排序就像是把一堆乱七八糟的物品按照大小堆成一堆，然后一层一层地取出最大的（或最小的）物品。首先，我们把所有的物品都堆在一起，然后把最大的物品放在最上面。接着，我们把最大的物品取出来，再从剩下的物品中找出最大的，放在第二个位置。我们重复这个过程，直到所有的物品都被有序地取出。
这个过程的关键在于，我们需要把物品堆成一个堆，然后一层一层地取出最大的（或最小的）物品。堆的构建是通过不断地比较和交换物品的位置来完成的。当我们把物品堆成堆后，每次取出最大的（或最小的）物品只需要一层一层地向上移动，直到找到堆的根节点，然后把根节点取出来，再从剩下的物品中重新堆成一个新的堆。
// 向下调整 void AdjustDown(int* a, int n, int parent) { int child = parent / 2 + 1; // 初始化子节点的索引 while (child < n) // 当子节点存在时 { if (child + 1 < n && a[child + 1] > a[child]) // 如果存在右子节点并且右子节点的值大于左子节点的值 { ++child; // 更新子节点索引为右子节点 } if (a[child] > a[parent]) // 如果子节点的值大于父节点的值 { swap(&a[child], &a[parent]); // 交换父节点和子节点的值 parent = child; // 更新父节点索引为子节点索引 child = parent * 2 + 1; // 重新初始化子节点索引为父节点的左子节点 } else { break; // 如果父节点的值大于或等于子节点的值，跳出循环 } } } // 堆排序 void HeapSort(int* a, int n) { // 升序建大堆 // 降序建小堆 // 向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) // 从最后一个非叶子节点的父节点开始向下调整 { AdjustDown(a, n, i); // 向下调整堆 } int end = n - 1; // 初始化最后一个元素的索引 while (end > 0) // 当还有元素未排序时 { swap(&a[0], &a[end]); // 交换堆顶元素（最大值）和堆底元素 AdjustDown(a, end, 0); // 调整堆，使得堆顶元素（最大值）保持在正确的位置 --end; // 减少堆的大小，因为堆顶元素已经移除 } }AdjustDown函数用于向下调整堆，确保父节点的值不大于子节点的值。这个函数在HeapSort函数中用于构建大堆。HeapSort函数首先调用AdjustDown函数从最后一个非叶子节点的父节点开始向下调整，构建大堆。然后，
HeapSort函数开始排序过程。在排序过程中，它首先将堆顶元素（最大值）与堆底元素交换，然后调用AdjustDown函数调整堆，确保堆顶元素保持在正确的位置。重复交换和调整堆的过程，每次都将一个元素移到已排序部分，直到所有的元素都被排序。
最好情况：当输入数组已经是排序好的，算法只需要遍历一次，时间复杂度为O(n)。
最坏情况：当输入数组是逆序的，算法需要遍历n次，每次遍历都需要进行n-1次比较和交换，时间复杂度为O(n^2)。
平均情况：由于最好情况和最坏情况已经涵盖了所有情况，平均时间复杂度也为O(n^2)。
因此，堆排序不是一个高效的排序算法，但它简单易懂，适用于小规模或基本已排序的数据。
快速排序
任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
你把所有的物品都堆在一起，然后从中挑出第一个一个物品，这个物品就是我们要找的“基准”或者“参照物”。接下来，你把所有比这个物品大的物品都放在它的左边，把所有比这个物品小的物品都放在它的右边。这样，左边的就是比基准大的物品，右边的就是比基准小的物品。然后，你分别对左右两边的物品进行快速排序，直到所有的物品都被有序地排列好。
主要就是找基准
int PartSort1(int a[], int left, int right) { int keyi = left; while (left < right) { //右边找小 while (left < right && a[right] >= a[keyi]) { right--; } //左边找大 while (left < right && a[left] <= a[keyi]) { left++; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); return left; } void QuickSort(int a[], int begin, int end) { if (begin >= end) { return; } int keyi = PartSort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }为什么是“>=”,"<=",等号能去掉吗？
不能！！！考虑这样一种情况，如果去掉等号，right在找小的过程中，遇到了和key相等的值就会停下。而left在找大的过程恰好也停在和key相等的位置，left和right交换，进行下一轮循环，right和left在原地又会进行交换，如此就陷入了死循环……
冒泡排序（左右比较）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个相邻元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
思路： 1.比较相邻的元素。如果第一个比第二个大，就交换它们两个； 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 3.针对所有的元素重复以上的步骤，除了最后一个； 4.重复步骤1~3，直到数组有序，排序完成。
/* 冒泡排序 */ void BubbleSort(int arr[], int length) // arr： 需要排序的数组； length： 数组长度 //注： int cnt = sizeof(a) / sizeof(a[0]);获取数组长度 { for (int i = 0; i < length; i++) { for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp; temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } 平均时间复杂度: T(n) = O(n²) 最坏时间复杂度: T(n) = O(n²)：当输入的数据是反序时 最好时间复杂度: T(n) = O(n)：当输入的数据已经有序时，只需遍历一遍用于确认数据已有序。 空间复杂度: O(1) 稳定性: 稳定
快速排序优化
如果数组是随机的，无序的，会很接近二分的情况。但如果数组是有序的，每次都选择最左边的元素作为key，那么key的最终位置不变，共有n-1趟排序，时间复杂度是等差数列求和，O(n^2)
为了应对这种特殊情况，我们需要保证每次选择的key不是所有数中的最值，尽可能取一个中位数就好了。于是提出随机数取中的办法，即每一次选择两端的数和他们中间的任意一个数，比较他们的大小，取中间的数作为key。
int GetMidIndex(int a[], int begin, int end) { int mid = begin + rand() % (end - begin); if ((a[mid] >= a[begin] && a[mid] <= a[end]) || (a[mid] <= a[begin] && a[mid] >= a[end])) { return mid; } if ((a[begin] >= a[mid] && a[begin] <= a[end]) || (a[begin] <= a[mid] && a[begin] >= a[end])) { return begin; } return end; }还有一种情况，如果所有的数都相同，随机数取中也没有效果，时间复杂度仍为O(n^2),这时可以采用三路划分的办法，即将数组划分成小于key，等于key和大于key的三部分。思想和前后指针法是类似的，前后指针法实际是划分成小于key和大于等于key两部分。
int PartSort(int a[], int begin, int end) { int key = a[begin]; int left = begin - 1;//小于key的最后一个位置 int right = end + 1;//大于key的最前一个位置 int cur = begin;//遍历区间 //[begin, left][left+1, cur-1][right, end] while (cur < right) { if (a[cur] < key) { Swap(&a[++left], &a[cur]); cur++; } else if (a[cur] > key) { Swap(&a[--right], &a[cur]); } else { cur++; } } }归并排序
基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
void _MergeSort(int a[], int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) / 2; _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); //归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin1; while (begin1 <= end1 && begin2 <= end2) { //谁小谁尾插 if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //拷贝回a数组 memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } 计数排序计数排序
统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中
void CountSort(int a[], int n) { int min = a[0], max = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int* countA = calloc(range, sizeof(int)); if (countA == NULL) { perror("malloc fail"); return; } //计数 for (int i = 0; i < n; i++) { countA[a[i] - min]++; } //排序 int k = 0; for (int i = 0; i < range; i++) { while (countA[i]--) { a[k++] = i + min; } } }时间复杂度和空间复杂度
时间复杂度：一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。则有T(N) = O(f(N))，这称作算法的渐进时间复杂度，简称时间复杂度
空间复杂度：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
了解算法的每个步骤、循环、递归调用等。
时间复杂度分析：
最好情况：分析算法在输入数据已经有序或其他最理想情况下所需的时间。
最坏情况：分析算法在输入数据完全无序或其他最糟糕情况下所需的时间。
平均情况：分析算法在所有可能输入数据情况下所需时间的平均值。
空间复杂度分析：
最好情况：分析算法在内存使用最少的情况下的空间需求。
最坏情况：分析算法在内存使用最多的情况下的空间需求。
平均情况：分析算法在所有可能情况下的平均内存使用量。
时间复杂度和空间复杂度都与多种因素息息相关，这些因素可以影响算法执行的效率。
时间复杂度：
循环和递归：循环和递归的次数是影响时间复杂度的重要因素。循环的次数越多，算法执行的时间就越长。递归的深度也决定了算法执行的时间。
基本操作：算法中执行次数最多的基本操作决定了时间复杂度。例如，在冒泡排序中，比较和交换操作的次数决定了算法的时间复杂度。
数据结构：算法操作的数据结构也会影响时间复杂度。例如，数组和链表的操作时间复杂度不同。
算法设计：算法的效率也受到算法设计的影响。一个高效的设计可以减少不必要的操作，从而降低时间复杂度。
空间复杂度：
额外空间：算法执行过程中所需的额外空间会影响空间复杂度。例如，排序算法中用于存储临时数据的额外空间。**
数据结构：与时间复杂度类似，操作不同数据结构也会影响空间复杂度。例如，链表和数组在存储空间上的差异。
递归深度：递归算法中，递归调用的深度直接决定了栈空间的使用，进而影响空间复杂度。
总的来说，时间复杂度和空间复杂度是算法效率的两个重要方面，它们受到算法设计、基本操作、数据结构以及循环和递归等因素的影响。在选择或设计算法时，需要综合考虑这些因素，以找到最合适的解决方案。
对于冒泡排序算法
时间复杂度：
最好情况：如果输入数组已经是排序好的，冒泡排序只需要进行一次遍历，时间复杂度为O(n)。
最坏情况：如果输入数组是逆序的，冒泡排序需要进行n-1次遍历，每次遍历都需要进行n-1次比较和交换，时间复杂度为O(n^2)。
平均情况：由于最好情况和最坏情况已经涵盖了所有情况，平均时间复杂度也为O(n^2)。
空间复杂度：冒泡排序只需要常数级别的额外空间来存储临时变量，因此空间复杂度为O(1)。
