大佬教程收集整理的这篇文章主要介绍了《算法》学习笔记(一),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
算法思想 找到数组中最小的元素,将其与数组第一个元素交换,再不断的在剩下的元素中进行重复,最后将数组排序。
复杂度考虑 假设数组的元素为N个,从0~N - 1的任意一个元素i都需要进行一次交换和N - 1 - i 次比较,总共就是N次交换和 (N^2-1) 次比较。因此时间复杂度为(O(n^2))。
代码实现(C++)
template <typename T>
void SELEctSort(vector<T> &a)
{
int n = a.size();
for (int i = 0; i < n; i++)
{
int min = i;
for (int j = i + 1; j < n; j++) //寻找剩余元素中的最小元素
{
if (a[j] < a[min])
min = j;
}
swap(a[i], a[min]);
}
return;
}
算法思想 将待排序的数组分为有序部分和无序部分,在开始时,认为第一个元素是有序的,在无序元素中将无序部分的元素插入有序部分的合理位置,当遍历完无序部分时,即完成排序。
复杂度考虑 假设数组有N个元素,平均情况下,对于索引为1~N - 1中的任意元素 i 的要进行 (frac{i-1}{2}) 次比较,因此时间复杂度为(O(n^2))。
代码实现(C++)
template <typename T>
void InsertSort(vector<T> &a)
{
int n = a.size();
for (int i = 1; i < n; i++)
{
int temp = a[i];
int j = i - 1;
while (j >= 0 && a[j] > temp)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
return;
}
算法思想: 希尔排序是一种基于插入排序的快速排序方法。取数组中任意间隔为gap,将待排序的元素分为以gap为长度的子数组,然后对各子数组进行直接插入排序,然后逐渐减小gap的值,不断重复分组和排序,最后当gap = 1时,排序完成。
复杂度考虑: 希尔排序的时间复杂度与gap的选取有关,当gap=1时,退化为直接插入排序,复杂度为(O(n^2)),而取Hibbard增量(1,3,5,7...)时,在最坏情况下时间复杂度为(O(n^{frac{3}{2}}))。
稳定性
对于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,因此,SHell排序是不稳定的。
代码实现(C++)
template <typename T>
void SHellSort(vector<T> &a)
{
int n = a.size();
int h = n / 2;
while (h >= 1)
{
for (int i = h; i < n; i++)
{
for (int j = i; j >= h && a[j] < a[j - h]; j -= h)
swap(a[j], a[j - h]);
}
h /= 2;
}
return;
}
算法思想
将数组递归地分成两半分别排序,然后将其归并起来。
归并操作
直接将两个不同的有序数组归并到第三个数组
template <typename T>
void merge(vector<T> &a, int low, int mid, int high) //归并
{
int n = a.size();
vector<T> aux(n);
for (int i = low; i <= high; i++) //拷贝数组
aux[i] = a[i];
int i = low, j = mid + 1;
for (int k = low; k <= high; k++)
{
if (i > mid)
a[k] = aux[j++];
else if (j > high)
a[k] = aux[i++];
else if (aux[i] < aux[j])
a[k] = aux[i++];
else
a[k] = aux[j++];
}
}
图示1:将数组A和数组B归并
@H_801_105@
for循环内的四个条件判断分别是:
自顶向下的归并
自顶向上的归并
先归并微型数组,然后再成对归并得到的子数组,不断往复,将整个数组归并在一起。
template <typename T>
void MergeSort(vector<T> &a) //迭代归并
{
int n = a.size();
vector<T> aux(a); //拷贝数组
for(int sz = 1; sz < n; sz+=sz) //sz为子数组大小
{
for(int i = 0; i < n-sz; i+= sz*2) //i为子数组索引
{
merge(a,i,i+sz-1,min(i+2*sz-1,n-1)); //最后一次子数组的大小可能比sz小
}
}
}
数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | @H_616_175@
---|---|---|---|---|---|---|---|---|
原数组 | 3 | 44 | 38 | 5 | 47 | 15 | 10 | 21 | @H_616_175@
3 | 44 | 38 | 5 | 47 | 15 | 10 | 21 | @H_616_175@|
3 | 44 | 5 | 38 | 47 | 15 | 10 | 21 | @H_616_175@|
3 | 44 | 5 | 38 | 15 | 47 | 10 | 21 | @H_616_175@|
3 | 44 | 5 | 38 | 15 | 47 | 10 | 21 | @H_616_175@|
3 | 5 | 38 | 44 | 15 | 47 | 10 | 21 | @H_616_175@|
3 | 5 | 38 | 44 | 10 | 15 | 21 | 47 | @H_616_175@|
3 | 5 | 10 | 15 | 21 | 38 | 44 | 47 | @H_616_175@
复杂度考虑
算法优化
对小规模数组使用插入排序
测试数组是否有序
不将元素复制到辅助数组
代码实现(C++)
template <typename T>
void MergeSort(vector<T> &a, int low, int high) //改良版归并排序
{
int mid = low + (high - low) / 2;
if(high - low <= 3) //小规模数组使用插入排序
{
for(int i = low; i <= high; i++)
{
for(int j = i; j > low && a[j] < a[j-1]; j--)
swap(a[j],a[j-1]);
}
return;
}
MergeSort(a,low,mid);
MergeSort(a,mid+1,high);
if(!a[mid] < a[mid+1])
merge(a,low,mid,high);
}
算法思想:快速排序也是分治思想的排序算法,将数组分为三段,左段,分割元素,右段。左段的元素都不大于分割元素,右段的元素都不小于分割元素,然后对左段和有段独立排序。
复杂度考虑
快速排序需要的递归栈空间为(O(n)),若用栈来模拟递归,则需要的空间可以减少为(O(logn))。
在最坏情况下,数据段左段总为空,此时用时为(O(n^2))。在最好情况下,左段和右端的元素数目总是大致相同,此时用时(O(nlogn))。平均复杂度为(O(nlogn))。
代码实现(C++)
template <typename T>
int Partition(vector<T> &a, int low, int high) //切分
{
int i = low, j = high + 1;
T temp = a[low]; //切分元素
while (true)
{
//扫描左右
while (a[++i] < temp)
;
while (a[--j] > temp)
;
if (i >= j) //i,j相遇时终止循环
break;
swap(a[i], a[j]);
}
swap(a[low],a[j]);
return j;
}
template <typename T>
void QuickSort(vector<T> &a, int low, int high) //快速排序
{
if (low >= high)
return;
int j = Partition(a, low, high);
QuickSort(a, low, j - 1); //左段排序
QuickSort(a, j + 1, high); //右段排序
}
算法改进
代码实现(C++)
template <typename T>
void QuickSort_inThreeWays(vector<T> &a, int low, int high) //三路切分的快速排序
{
if (low >= high)
return;
int lt = low, i = low, gt = high;
T pivot = a[low];
while (i <= gt)
{
//索引元素与分割元素进行比较,来判断索引所处的部分
int temp = (a[i] > pivot) ? 1 : ((a[i] == pivot) ? 0 : -1);
if (temp < 0)
swap(a[lt++], a[i++]);
else if (temp > 0)
swap(a[gt--], a[i]);
else
i++;
}
QuickSort_inThreeWays(a, low, lt - 1);
QuickSort_inThreeWays(a, gt + 1, high);
}
我们经常需要处理有序的元素,但又不一定要求他们全都有序,或者要一次性的就将它们排序。很多时候我们只需要处理一些元素中键值最大或者键值最小的元素。 这种时候合适的数据结构应该支持插入和删除最大(最小)元素。 这种类型的数据类型叫优先队列。接下来主要使用以堆实现的优先队列。
堆的定义
堆的算法
在堆的有序化中,我们会遇到某个结点的优先级上升和某个结点优先级下降两种情况。这个时候我们需要采用自下而上恢复堆的有序化和自上而下恢复堆的有序化。
上浮(自下而上的堆有序化)
下沉(自上而下的堆有序化)
优先队列的代码实现(C++)
template <typename T>
class Proiority_Queue
{
private:
vector<T> pq;
int n = 0;
public:
Proiority_Queue(int n)
{
pq.assign(n + 1, null); //开辟数组空间
}
bool isEmpty() { return N == 0; }
int Size() { return N; }
void insert(T value)
{
pq[++N] = value; //在子结点插入新结点
swim(N); //寻找
}
T delMax()
{
T max = pq[1];
swap(pq[1], pq[N--]);
pq[N + 1].~T();
sink(1);
return max;
}
void swim(int k) //上浮
{
while (k > 1 && pq[k / 2] < pq[k])
{
swap(pq[k / 2], pq[k]);
k /= 2;
}
}
void sink(int k) //下沉
{
int n = pq.size();
while (2 * k <= n)
{
int j = 2 * k;
if (j < n && pq[j] < pq[j + 1])
j++;
if (pq[k] >= pq[j])
break;
swap(pq[k], pq[j]);
k = j;
}
}
};
复杂度考虑
堆排序
堆的构造
代码实现C(++)
template <typename T>
void HeapSort(vector<T> &a)
{
int n = a.size();
for (int i = n / 2; i >= 1; i--)
{
sink(a, i);
while (n > 1)
{
swap(a[1], a[n--]);
sink(a, 1);
}
}
}
复杂度考虑
冒泡排序
计数排序
算法思想
代码描述(C++)
void CounTingSort(vector<int> nums)
{
int minn = INT_MAX, maxn = INT_MIN;
for(int num : nums) //寻找最大最小值
{
minn = min(minn,num);
maxn = max(maxn,num);
}
vector<int> cnt(maxn - minn + 1); //建立新数组
for(int num : nums) //统计每个元素出现次数
{
cnt[num-minn]++;
}
int cur = 0;
for(int i = 0; i < cnt.size(); i++) //根据出现次数把cnt数组放回旧数组
{
while(cnt[i]>0)
{
nums[cur++] = i + minn;
cnt[i]--;
}
}
}
桶排序
基数排序
排序算法的性能特点
算法 | 是否稳定 | 时间复杂度 | 空间复杂度 | @H_616_175@
---|---|---|---|
冒泡排序 | 稳定 | (O(n^2)) | (O(1)) | @H_616_175@
选择排序 | 否 | (O(n^2)) | (O(1)) | @H_616_175@
插入排序 | 是 | (O(n^2)) | (O(1)) | @H_616_175@
希尔排序 | 否 | (O(nlogn)) | (O(1)) | @H_616_175@
快速排序 | 否 | (O(nlogn)) | (O(nlogn)) | @H_616_175@
归并排序 | 是 | (O(nlogn)) | (O(n)) | @H_616_175@
堆排序 | 否 | (O(nlogn)) | (O(1)) | @H_616_175@
计数排序 | 是 | (O(n+k)) | (O(n+k)) | @H_616_175@
桶排序 | 是 | (O(n+k)) | (O(n+k)) | @H_616_175@
基数排序 | 是 | (O(n*k)) | (O(n+k)) | @H_616_175@
以上是大佬教程为你收集整理的《算法》学习笔记(一)全部内容,希望文章能够帮你解决《算法》学习笔记(一)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。